Enhancing Sparsity by Reweighted ℓ1 Minimization
By E.J. Candes, Michael B. Wakin, Stephen P. Boyd. 2007
5,262 citations recorded by the source corpus.
It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained ℓ1 minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms ℓ1 minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted ℓ1-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations—not by reweighting the ℓ1 norm of the coefficient sequence as is common, but by reweighting the ℓ1 norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as Compressive Sensing.
Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- E.J. Candes
- Yonina C. Eldar
- Justin K. Romberg
- Gitta Kutyniok
- Zhouchen Lin
- René Vidal
- Shuicheng Yan
- Bhaskar D. Rao
In Computational Mechanics
- Lei Zhang
- Francis R. Bach
- Julien Mairal
- E.J. Candes
- Wangmeng Zuo
- Wotao Yin
- Zhouchen Lin
- Shuicheng Yan
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Lei Zhang
- Dacheng Tao
- Ming-Hsuan Yang
- Xiaogang Wang
- Chen Change Loy
- Yi Yang
- Trevor Darrell
Citations in the corpus
- BayesNAS: A Bayesian Approach for Neural Architecture Search (2019, methodology): “• Simple and fast search: Our algorithm is formulated simply as an iteratively re-weighted `1 type algorithm (Candes et al., 2008) where the re-weighting coefficients used for the next iteration are computed not only from the value of the current solution but also from its posterior variance.”
- Best Subset Selection via a Modern Optimization Lens (2015, methodology): “To address the shortcomings, non-convex penalized regression is often used to “bridge” the gap between the convex `1 penalty and the combinatorial `0 penalty [38, 27, 24, 54, 55, 28, 61, 62, 57, 13].”
- Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “Then, we show that our approach provides an effective incremental DC programming algorithm, which we apply to sparse estimation problems with nonconvex penalties [10].”
- Optimization with Sparsity-Inducing Penalties (2011, background): “Such algorithmic schemes appear early in the optimization literature under the name DC (difference of convex) programming (see [48] and references therein), and were recently revisited in reweighted-l1 algorithms [29].”
- Optimal Transport for Domain Adaptation (2014, methodology): “Ω(γ) ≤ Ω̃(γ) = 〈γ,G〉F + cst (11) where the matrix G has components G(Ic, j) = p(‖γ̂(Ic, j)‖+ )p−1, ∀c, j (12) We added a small > 0 that helps avoiding numerical instabilities, as discussed in [26].”
- MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels (2017, background): “In the special cases, ρ ( ‘ ) degenerates to the classical robust M-estimator: Huber (Huber et al., 1964) and the log-sum penalty (Candes et al., 2008).”
- Sparse Recovery of Streaming Signals Using $\ell_1$-Homotopy (2013, methodology): “We use the available signal estimate to aide the recovery process in two ways: We update the Wt using available estimates of the sparse coefficients αt (in the same spirit as iterative reweighting [16]), and we use the available estimates of the αt as a starting point to expedite the solution of the”
- On Security Indices for State Estimators in Power Networks (2010, background): “Remark 1: It is possible to include resistive losses in (1) and shunt loads in (2), see [2], but to simplify notation we leave this out.”
- Sparse LMS for system identification (2009, methodology): “The log-sum penalty N i=1 log(1 + |wi|/ε ) has been introduced as it behaves more similarly to the 0 norm than ‖w‖1 [11].”
- What Objective Does Self-paced Learning Indeed Optimize? (2015, methodology): “Such decomposition not only simplifies the solving of the problem as an easy re-weighted strategy [4], but makes it feasible to embed helpful loss prior knowledge into an SPL scheme.”
- Sparse Representation for Computer Vision and Pattern Recognition (2010, background): “In addition, these costs can be replaced by a (nonconvex) Lorentzian penalty function, motivated either by further approximating the ‘ by ‘(1) [19], or by considering a mixture of Laplacians prior for the coefficients in A and exploiting MDL concepts [67], instead of the more classical Laplacian pri”
- A BaSiC tool for background and shading correction of optical microscopy images (2017, background): “Besides, the minimization of an L0-norm is NP-hard 13 .”
- Enhanced lasso recovery on graph (2015, background): “er that the recovery performance depends also on the incoherence property about the number of observed measurements. In this context, the major motivation to go beyond convexity with the recent works [7, 8, 9] is to precisely improve sparse recovery with a smaller number of measurements than the sta”
- Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation (2014, background): “reweighted ‘1 minimization problem [22] as S0-‘1-W.”
- NESTA: A Fast and Accurate First-Order Method for Sparse Recovery (2009, background): “1) is given by f(x) = ‖Wx‖`1 , where one may think of W as a short-time Fourier transform also known as the Gabor transform, a curvelet transform, an undecimated wavelet transform and so on, or a combination of these, or a general arbitrary dictionary of waveforms (note that this class of recovery p”
- Sparse Bayesian multi-task learning for predicting cognitive outcomes from neuroimaging measures in Alzheimer's disease (2012, background): “Second, one can see (30) is an MMV-model based iterative reweighted l1 minimization algorithm [3], since its weights w i depends on the estimate of X in the previous iteration.”