Iteratively reweighted least squares minimization for sparse recovery

By Ingrid Daubechies, Ronald A. DeVore, Massimo Fornasier, C. Sinan Güntürk. 2008

1,398 citations recorded by the source corpus.

Under certain conditions (known as the restricted isometry property, or RIP) on the m × N matrix Φ (where m < N), vectors x ∈ ℝN that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y := Φx even though Φ−1(y) is typically an (N − m)—dimensional hyperplane; in addition, x is then equal to the element in Φ−1(y) of minimal 𝓁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 Φ−1(y) with smallest 𝓁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) := [|x i(n) |2 + ε n2 ]−1/2, i = 1, …, N, for a decreasing sequence of adaptively defined εn; this updated weight is then used to obtain x(n + 1) and the process is repeated. We prove that when Φ satisfies the RIP conditions, the sequence x(n) converges for all y, regardless of whether Φ−1(y) contains a sparse vector. If there is a sparse vector in Φ−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) = [|x i(n) |2 + ε n2 ]−1+τ/2, i = 1, …, N, where 0 < τ < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for τ approaching 0. © 2009 Wiley Periodicals, Inc.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/f26b1a228679cd54b2392cc74436d6dbc072937e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

AVO inversion and poroelasticity with P- and S-wave moduli (2012, methodology): “We solve equation 24 with the IRLS method (Daubechies et al., 2010).”
Optimization for machine learning (2010, background): “In this section, we show on our motivating example of sums of l2-norms of subsets how such formulations arise (see, e.g. Pontil et al., 2007; Rakotomamonjy et al., 2008; Jenatton et al., 2010b; Daubechies et al., 2010).”
Weiszfeld’s Method: Old and New Results (2014, methodology): “This scheme was studied in in the context of various types of models and the literature of this method covers hundreds of paper that were written in the past 60 years; the list of references [2, 19, 30, 38, 44] is just a very small representative sample of works dealing with various applications and”
Saliency Detection via a Multiple Self-Weighted Graph-Based Manifold Ranking (2020, neutral): “That is to say, the first term of (7) can be seen as an iteratively re-weighted method [48] with which to optimize (8).”
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning (2017, background): “Note that in [41], convergence was established under the condition that none of the xi ’s are zero, and in [42] the weight was adaptively modified so that it never goes to infinity.”
Iterative reweighted algorithms for matrix rank minimization (2012, methodology): “For p= 1, a theoretical guarantee for sparse recovery has been given for IRLS-p (Daubechies et al., 2010), similar to the guarantees for l1 minimization.”
Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals (2009, background): “It is known that IRLS converges linearly for certain signal recovery problems [15].”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “The regularizers can be some sparse inducing functions [13,3,75,76, 73] such as MCP, SCAD, lq and etc.”
Combinatorial Penalties: Structure preserved by convex relaxations (2017, background): “For example, `α-quasi-norms [24, 14] or more generally penalties of the form Φ(w) = ∑d i=1 φ(|wi|), where φ is a monotone concave penalty [12, 8, 16] can be more advantageous than the `1-norm.”
Compressive Sensing with structured random matrices (2012, methodology): “We refer the interested reader to [32, 33, 34, 43, 47, 76] for further efficient algorithms for `1-minimization.”
A Bilevel Optimization Approach for Parameter Learning in Variational Models (2013, methodology): “Motivated by the fixed-point algorithm for solving the lower-level 1 problems [32, 8], we consider a sequence of reweighted 2 problems for learning the optimal regularization parameters of the 1 problem.”
Optimization with Sparsity-Inducing Penalties (2011, neutral): “, [41, 55, 70, 109, 110]).”
Learning k for kNN Classification (2017, methodology): “The objective function Equation (6) is convex but non-smooth, and this article employs the framework of Iteratively Reweighted Least Square [Daubechies et al. 2010] to optimize Equation (6) as follows.”