Celebratio Mathematica

I. Daubechies, R. DeVore, M. Fornasier, and S. Gunturk: “Iteratively re-weighted least squares minimization: Proof of faster than linear rate for sparse recovery,” pp. 26–29 in 2008 42nd annual conference on information sciences and systems (Princeton, NJ, 19–21 March 2008). IEEE (Piscataway, NJ), 2008. incollection

Given an \( m{\times}N \) matrix \( \Phi \), with \( m < N \), the system of equations \( \Phi x = y \) is typically underdetermined and has infinitely many solutions. Various forms of optimization can extract a “best” solution. One of the oldest is to select the one with minimal \( \ell_2 \) norm. It has been shown that in many applications a better choice is the minimal \( \ell_1 \) norm solution. This is the case in Compressive Sensing, when sparse solutions are sought.

The minimal \( \ell_1 \) norm solution can be found by using linear programming; an alternative method is Iterative Re-weighted Least Squares (IRLS), which in some cases is numerically faster. The main step of IRLS finds, for a given weight \( w \), the solution with smallest \( \ell_2(w) \) norm; this weight is updated at every iteration step: if \( x^{(n)} \) is the solution at step \( n \), then \( w^{(n)} \) is defined by \[ w_i^{(n)} := \frac1{|x_i^{(n)}|},\quad i = 1,\dots,N .\]

We give a specific recipe for updating weights that avoids technical shortcomings in other approaches, and for which we can prove convergence under certain conditions on the matrix \( \Phi \) known as the Restricted Isometry Property. We also show that if there is a sparse solution, then the limit of the proposed algorithm is that sparse solution. It is also shown that whenever the solution at a given iteration is sufficiently close to the limit, then the remaining steps of the algorithm converge exponentially fast. In the standard version of the algorithm, designed to emulate \( \ell_1 \)-minimization, the exponential rate is linear; in adapted versions aimed at \( \ell_{\tau} \)-minimization with \( \tau < 1 \), we prove faster than linear rate.

Massimo Fornasier	Related
Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related

I. Daubechies, M. Fornasier, and I. Loris: “Accelerated projected gradient method for linear inverse problems with sparsity constraints,” J. Fourier Anal. Appl. 14 : 5–6 (2008), pp. 764–792. MR 2461606 Zbl 1175.65062 ArXiv 0706.4297 article

Regularization of ill-posed linear inverse problems via \( \ell_1 \) penalization has been proposed for cases where the solution is known to be (almost) sparse. One way to obtain the minimizer of such an \( \ell_1 \) penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to \( \ell_1 \)-constraints, using a gradient method, with projection on \( \ell_1 \)-balls. The corresponding algorithm uses again iterative soft-thresholding, now with a variable thresholding parameter. We also propose accelerated versions of this iterative method, using ingredients of the (linear) steepest descent method. We prove convergence in norm for one of these projected gradient methods, without and with acceleration.

Massimo Fornasier	Related
Ignace Loris	Related

I. Daubechies, R. DeVore, M. Fornasier, and C. S. Güntürk: “Iteratively reweighted least squares minimization for sparse recovery,” Comm. Pure Appl. Math. 63 : 1 (2010), pp. 1–38. MR 2588385 Zbl 1202.65046 ArXiv 0807.0575 article

Under certain conditions (known as the restricted isometry property, or RIP) on the \( m{\times}N \) matrix \( \Phi \) (where \( m < N \)), vectors \( x\in\mathbb{R}^N \) that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from \( y := \Phi x \) even though \( \Phi^{-1}(y) \) is typically an \( (N-m) \)-dimensional hyperplane; in addition, \( x \) is then equal to the element in \( \Phi^{-1}(y) \) of minimal \( \ell_1 \)-norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining \( x \), as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector \( w \), the element in \( \Phi^{-1}(y) \) with smallest \( \ell_2(w) \)-norm. If \( x^{(n)} \) is the solution at iteration step \( n \), then the new weight \( w^{(n)} \) is defined by \[ w_i^{(n)} := \bigl[|x_i^{(n)}|^2 + \epsilon_n^2\bigr]^{-1/2} ,\] \( i = 1, \dots,N \), for a decreasing sequence of adaptively defined \( \epsilon_n \); this updated weight is then used to obtain \( x^{(n+1)} \) and the process is repeated. We prove that when \( \Phi \) satisfies the RIP conditions, the sequence \( x^{(n)} \) converges for all \( y \), regardless of whether \( \Phi^{-1}(y) \) contains a sparse vector. If there is a sparse vector in \( \Phi^{-1}(y) \), then the limit is this sparse vector, and when \( x^{(n)} \) is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight \[ w_i^{(n)} := \bigl[|x_i^{(n)}|^2 + \epsilon_n^2\bigr]^{-1 + \tau/2} ,\] \( i = 1,\dots,N \), where \( 0 < \tau < 1 \), can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for \( \tau \) approaching 0.

Massimo Fornasier	Related
Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related

M. Fornasier, J. Vybíral, and I. Daubechies: Robust and resource efficient identification of shallow neural networks by fewest samples. Preprint, April 2018. ArXiv 1804.01592 techreport

We address the structure identification and the uniform approximation of sums of ridge functions \( f(x)=\sum_{i=1}^m g_i(a_i\cdot x) \) on \( \mathbb{R}^d \), representing a general form of a shallow feed-forward neural network, from a small number of query samples. Higher order differentiation, as used in our constructive approximations, of sums of ridge functions or of their compositions, as in deeper neural network, yields a natural connection between neural network weight identification and tensor product decomposition identification. In the case of the shallowest feed-forward neural network, second order differentiation and tensors of order two (i.e., matrices) suffice as we prove in this paper. We use two sampling schemes to perform approximate differentiation–active sampling, where the sampling points are universal, actively, and randomly designed, and passive sampling, where sampling points were preselected at random from a distribution with known density. Based on multiple gathered approximated first and second order differentials, our general approximation strategy is developed as a sequence of algorithms to perform individual sub-tasks. We first perform an active subspace search by approximating the span of the weight vectors \( a_1,\dots \), \( a_m \). Then we use a straightforward substitution, which reduces the dimensionality of the problem from \( d \) to \( m \). The core of the construction is then the stable and efficient approximation of weights expressed in terms of rank-1 matrices \( a_i \otimes a_i \), realized by formulating their individual identification as a suitable nonlinear program. We prove the successful identification by this program of weight vectors being close to orthonormal and we also show how we can costructively reduce to this case by a whitening procedure, without loss of any generality.

Massimo Fornasier	Related
Jan Vybíral	Related

year	title	people

			clear

Ingrid Daubechies

Complete Bibliography

Works connected to Massimo Fornasier

Filter the Bibliography List