An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
By Ingrid Daubechies, Michel Defrise, Christine De Mol. 2003
5,379 citations recorded by the source corpus.
We consider linear inverse problems where the solution is assumed to have a sparse expansion on an arbitrary preassigned orthonormal basis. We prove that replacing the usual quadratic regularizing penalties by weighted 𝓁p‐penalties on the coefficients of such expansions, with 1 ≤ p ≤ 2, still regularizes the problem. Use of such 𝓁p‐penalized problems with p < 2 is often advocated when one expects the underlying ideal noiseless solution to have a sparse expansion with respect to the basis under consideration. To compute the corresponding regularized solutions, we analyze an iterative algorithm that amounts to a Landweber iteration with thresholding (or nonlinear shrinkage) applied at each iteration step. We prove that this algorithm converges in norm. © 2004 Wiley Periodicals, Inc.
Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics, Mathematical Optimization, Numerical Methods & Scientific Computing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
- Francis R. Bach
- Julien Mairal
- Lei Zhang
- E.J. Candes
- Wotao Yin
- Peter Richtárik
- Richard Baraniuk
- Stephen P. Boyd
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Lei Zhang
- Dacheng Tao
- Ming-Hsuan Yang
- Trevor Darrell
- Xiaogang Wang
- Jitendra Malik
- Andrew Zisserman
In Mathematical Physics
- Stephen P. Boyd
- Wotao Yin
- Thomas Pock
- Francis R. Bach
- Lei Zhang
- Stanley J. Osher
- Laurent Condat
- Antonin Chambolle
In Mathematical Optimization
- Julien Mairal
- Francis R. Bach
- Robert Tibshirani
- Paul Tseng
- Tong Zhang
- Stephen P. Boyd
- Thomas Pock
- Wotao Yin
In Numerical Methods & Scientific Computing
- Julien Mairal
- E.J. Candes
- Lei Zhang
- Thomas Pock
- Francis R. Bach
- Richard Baraniuk
- Gitta Kutyniok
- Mário A. T. Figueiredo
Citations in the corpus
- Pedestrian Detection with Unsupervised Multi-stage Feature Learning (2012, methodology): “Many efficient algorithms for solving the above convex system has been proposed in recent years [1, 6, 2, 26].”
- Optimization Methods for Large-Scale Machine Learning (2016, neutral): “8) [50, 39].”
- Interpretable Recurrent Neural Networks Using Sequential Sparse Recovery (2016, methodology): “Many algorithms have been proposed, e.g. [17, 18], for solving the LASSO problem (16).”
- Regularization Paths for Generalized Linear Models via Coordinate Descent (2010, background): “Early references include Fu (1998), Shevade and Keerthi (2003) and Daubechies et al. (2004).”
- Neural Expectation Maximization (2017, methodology): “Gradient backpropagation through inference updates has previously been addressed in the context of sparse coding with (Fast) Iterative Shrinkage/Tresholding Algorithms ((F)ISTA; [5, 27, 2]).”
- Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “In some cases, the proximal operator can be computed efficiently in closed form, for example, when f2 is the 1-norm; it yields the iterative soft-thresholding algorithm for sparse estimation [16].”
- Sparse additive models (2007, methodology): “Convergence properties of variants of this simple algorithm have been recently treated by Daubechies et al. (2004, 2007).”
- Importance Estimation for Neural Network Pruning (2019, methodology): “These methods belong to the family of Iterative Shrinkage and Thresholding Algorithms (ISTA) [3].”
- Curvelet-based POCS interpolation of nonuniformly sampled seismic records (2012, methodology): “There is a dilemma in our choice: the rigorous root of iterative soft thresholding has been established with a proven convergence, stability and many other important mathematical aspects, using arbitrary initialization (Daubechies et al., 2004).”
- The Convex Geometry of Linear Inverse Problems (2010, background): “Proximity operators have already been harnessed for fast algorithms involving the 1 norm [20, 21, 35, 40, 73] and the nuclear norm [12, 51, 71] where these maps can be quickly computed in closed form.”
- Learned D-AMP: Principled Neural Network based Compressive Image Recovery (2017, methodology): “To reiterate, in [12; 13] and [14] the authors unroll the iterative ISTA [15] and AMP [16] algorithms, respectively, and then treat parameters of the algorithm as weights to be learned.”
- 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.”
- From Denoising to Compressed Sensing (2014, methodology): “Therefore, lower cost iterative algorithms were developed; including matching pursuit [6], orthogonal matching pursuit [7], iterative hard-thresholding [8], compressive sampling matching pursuit [9], approximate message passing [10], and iterative soft-thresholding [11]–[16], to name just a few.”
- Compressed Sensing for Real-Time Energy-Efficient ECG Compression on Wireless Body Sensor Nodes (2011, methodology): “dient projection [26], iterative thresholding [27], and greedy approaches such as orthogonal matching pursuit (OMP) [28], [29].”
- A New TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithms for Image Restoration (2007, methodology): “, the proof of convergence of IST (which is monotonic for β = 1) in [20].”
- High-resolution prestack seismic inversion using a hybrid FISTA least-squares strategy (2013, methodology): “FISTA is based on the iterative shrinkage thresholding algorithm (ISTA) (Daubechies et al., 2004), an extension of the classical gradient algorithm to solve large-scale linear inverse problems in a simple way.”