The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation
Abstract
We propose a fast algorithm for solving the $\ell_1$-regularized minimization problem $\min_{x\in\mathbb{R}^n}\mu\|x\|_1+\|Ax-b\|^2_2$ for recovering sparse solutions to an undetermined system of linear equations $Ax=b$. The algorithm is divided into two stages that are performed repeatedly. In the first stage a first-order iterative “shrinkage” method yields an estimate of the subset of components of x likely to be nonzero in an optimal solution. Restricting the decision variables x to this subset and fixing their signs at their current values reduces the $\ell_1$-norm $\|x\|_1$ to a linear function of x. The resulting subspace problem, which involves the minimization of a smaller and smooth quadratic function, is solved in the second phase. Our code FPC_AS embeds this basic two-stage algorithm in a continuation (homotopy) approach by assigning a decreasing sequence of values to $\mu$. This code exhibits state-of-the-art performance in terms of both its speed and its ability to recover sparse signals.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Donoho, D. L. (2004) · Cited by 16,703
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
Matching pursuits with time-frequency dictionaries
Mallat, S. G., & Zhang, Z. (1993) · IEEE Transactions on Signal Processing · doi:10.1109/78.258082 · Cited by 9,112
Sparse MRI: The application of compressed sensing for rapid MR imaging
Lustig, M., Donoho, D., & Pauly, J. M. (2007) · Magnetic Resonance in Medicine · doi:10.1002/mrm.21391 · Cited by 6,952
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Candes, E. J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885507 · Cited by 6,839
An iterative thresholding algorithm for linear inverse problems with a sparsity constraint.
Daubechies, I., Defrise, M., & De Mol, C. (2004) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20042 · Cited by 4,958
Benchmarking optimization software with performance profiles
Dolan, E. D., & Moré, J. J. (2002) · Mathematical Programming · doi:10.1007/s101070100263 · Cited by 4,412
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
Needell, D., & Tropp, J. A. (2009) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2008.07.002 · Cited by 4,326
Greed is Good: Algorithmic Results for Sparse Approximation
Tropp, J. A. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834793 · Cited by 3,635
Figueiredo, M. A. T., Nowak, R. D., & Wright, S. J. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910281 · Cited by 3,524
Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization
Zhu, C., Byrd, R. H., Lu, P., & Nocedal, J. (1997) · ACM Transactions on Mathematical Software · doi:10.1145/279232.279236 · Cited by 3,462
Two-Point Step Size Gradient Methods
BARZILAI, J., & BORWEIN, J. M. (1988) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/8.1.141 · Cited by 2,873
Signal Recovery by Proximal Forward-Backward Splitting
Combettes, P. L., & Wajs, V. R. (2005) · Multiscale Modeling & Simulation · doi:10.1137/050626090 · Cited by 2,678
Efficient sparse coding algorithms
Lee, H., Battle, A., Raina, R., & Ng, A. Y. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0105 · Cited by 2,394
An Interior-Point Method for Large-Scale -Regularized Least Squares
Kim, S.-J., Koh, K., Lustig, M., Boyd, S., & Gorinevsky, D. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910971 · Cited by 2,083
A New TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithms for Image Restoration
Bioucas-Dias, J. M., & Figueiredo, M. A. T. (2007) · IEEE Transactions on Image Processing · doi:10.1109/tip.2007.909319 · Cited by 2,064 · cited 1×
“1), which has also been generalized to certain other nonsmooth functions; see [26, 5, 29, 63].”
BackgroundProbing the Pareto Frontier for Basis Pursuit Solutions
van den Berg, E., & Friedlander, M. P. (2009) · SIAM Journal on Scientific Computing · doi:10.1137/080714488 · Cited by 1,939
Sparse Reconstruction by Separable Approximation
Wright, S. J., Nowak, R. D., & Figueiredo, M. A. T. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016892 · Cited by 1,854
Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008) · SIAM Journal on Imaging Sciences · doi:10.1137/070703983 · Cited by 1,414
Self-citationJust relax: convex programming methods for identifying sparse signals in noise
Tropp, J. A. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.864420 · Cited by 1,407
An EM algorithm for wavelet-based image restoration
Figueiredo, M. A. T., & Nowak, R. D. (2003) · IEEE Transactions on Image Processing · doi:10.1109/tip.2003.814255 · Cited by 1,219
A Nonmonotone Line Search Technique for Newton’s Method
Grippo, L., Lampariello, F., & Lucidi, S. (1986) · SIAM Journal on Numerical Analysis · doi:10.1137/0723046 · Cited by 1,156
Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
Hale, E. T., Yin, W., & Zhang, Y. (2008) · SIAM Journal on Optimization · doi:10.1137/070698920 · Cited by 909
Self-citationNESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Becker, S., Bobin, J., & Candès, E. J. (2009) · Cited by 897
Gradient methods for minimizing composite objective function
Nesterov, Y. E. (2007) · Cited by 867
A coordinate gradient descent method for nonsmooth separable minimization
Tseng, P., & Yun, S. (2009) · Mathematical Programming · doi:10.1007/s10107-007-0170-0 · Cited by 728
Optimization Theory and Methods
(2006) · Springer Optimization and Its Applications · doi:10.1007/b106451 · Cited by 617
A Fast Alternating Direction Method for TVL1-L2 Signal Reconstruction From Partial Fourier Data
Yang, J., Zhang, Y., & Yin, W. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042333 · Cited by 571
Self-citationQuantitative Robust Uncertainty Principles and Optimally Sparse Decompositions
Candes, E. J., & Romberg, J. (2006) · Foundations of Computational Mathematics · doi:10.1007/s10208-004-0162-x · Cited by 504
A new compressive imaging camera architecture using optical-domain compression:
Takhar, D., Laska, J. N., Wakin, M. B., Duarte, M. F., Baron, D., Sarvotham, S., Kelly, K. F., & Baraniuk, R. G. (2006) · SPIE Proceedings · doi:10.1117/12.659602 · Cited by 497
Theory and Implementation of an Analog-to-Information Converter using Random Demodulation
Laska, J. N., Kirolos, S., Duarte, M. F., Ragheb, T. S., Baraniuk, R. G., & Massoud, Y. (2007) · 2007 IEEE International Symposium on Circuits and Systems (ISCAS) · doi:10.1109/iscas.2007.378360 · Cited by 412
Analog-to-Information Conversion via Random Demodulation
Kirolos, S., Laska, J., Wakin, M., Duarte, M., Baron, D., Ragheb, T., Massoud, Y., & Baraniuk, R. (2006) · 2006 IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software · doi:10.1109/dcas.2006.321036 · Cited by 393 · cited 1×
“For more information on compressive sensing, see, for example, [21, 54, 60, 61, 51, 41, 55, 37, 39, 38, 64].”
BackgroundOn the Solution of Large Quadratic Programming Problems with Bound Constraints
Moré, J. J., & Toraldo, G. (1991) · SIAM Journal on Optimization · doi:10.1137/0801008 · Cited by 335
An Architecture for Compressive Imaging
Wakin, M. B., Laska, J. N., Duarte, M. F., Baron, D., Sarvotham, S., Takhar, D., Kelly, K. F., & Baraniuk, R. G. (2006) · 2006 International Conference on Image Processing · doi:10.1109/icip.2006.312577 · Cited by 323
Why Simple Shrinkage Is Still Relevant for Redundant Representations?
Elad, M. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885522 · Cited by 291
Random Filters for Compressive Sampling and Reconstruction
Tropp, J. A., Wakin, M. B., Duarte, M. F., Baron, D., & Baraniuk, R. G. (2006) · 2006 IEEE International Conference on Acoustics Speed and Signal Processing Proceedings · doi:10.1109/icassp.2006.1660793 · Cited by 264
Algorithms for bound constrained quadratic programming problems
Mor�, J. J., & Toraldo, G. (1989) · Numerische Mathematik · doi:10.1007/bf01396045 · Cited by 230
Random Sampling for Analog-to-Information Conversion of Wideband Signals
Laska, J., Kirolos, S., Massoud, Y., Baraniuk, R., Gilbert, A., Iwen, M., & Strauss, M. (2006) · 2006 IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software · doi:10.1109/dcas.2006.321048 · Cited by 225
Elad, M., Matalon, B., & Zibulevsky, M. (2007) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.02.002 · Cited by 201
Proximal Thresholding Algorithm for Minimization over Orthonormal Bases
Combettes, P. L., & Pesquet, J.-C. (2008) · SIAM Journal on Optimization · doi:10.1137/060669498 · Cited by 190
A l 1-Unified Variational Framework for Image Restoration
Bect, J., Blanc‐Féraud, L., Aubert, G., & Chambolle, A. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24673-2_1 · Cited by 150
Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization
Tseng, P., & Yun, S. (2008) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-008-9458-3 · Cited by 144
Byrd, R. H., Gould, N. I. M., Nocedal, J. M., & Waltz, R. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0485-4 · Cited by 139
A wide-angle view at iterated shrinkage algorithms
Elad, M., Matalon, B., Shtok, J., & Zibulevsky, M. (2007) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.741299 · Cited by 112
Fixed-Point Continuation Applied to Compressed Sensing: Implementation and Numerical Experiments
Hale, E. T., Yin, W., & Zhang, Y. (2009) · Journal of Computational Mathematics · doi:10.4208/jcm.2009.10-m1007 · Cited by 68
Self-citationFast wavelet-based image deconvolution using the EM algorithm
Nowak, R. D., & Figueiredo, M. A. T. (2001) · 2018 52nd Asilomar Conference on Signals, Systems, and Computers · doi:10.1109/acssc.2001.986953 · Cited by 67
A note on wavelet-based inversion algorithms
Mol, C. D., & Defrise, M. (2002) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/313/05370 · Cited by 48
Two-Step Algorithms for Linear Inverse Problems with Non-Quadratic Regularization
Bioucas‐Dias, J. M., & Figueiredo, M. A. T. (2007) · Proceedings - International Conference on Image Processing · doi:10.1109/icip.2007.4378902 · Cited by 35
Cited by
Fixed point and Bregman iterative methods for matrix rank minimization
Ma, S., Goldfarb, D., & Chen, L. (2011) · Mathematical Programming · doi:10.1007/s10107-009-0306-5 · Cited by 1,048
Self-citationComputational Methods for Sparse Solution of Linear Inverse Problems
Tropp, J. A., & Wright, S. J. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2044010 · Cited by 1,046
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Becker, S., Bobin, J., & Candès, E. J. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090756855 · Cited by 848
Templates for convex cone problems with applications to sparse signal recovery
Becker, S. R., Candès, E. J., & Grant, M. C. (2011) · Mathematical Programming Computation · doi:10.1007/s12532-011-0029-5 · Cited by 608
Minimization of $\ell_{1-2}$ for Compressed Sensing
Yin, P., Lou, Y., He, Q., & Xin, J. (2015) · SIAM Journal on Scientific Computing · doi:10.1137/140952363 · Cited by 473
Metadata
- Authors
- Wen, Z., Yin, W., Goldfarb, D., & Zhang, Y.
- Venue
- SIAM Journal on Scientific Computing
- Published
- 2010-01
- Volume
- 32
- Issue
- 4
- Pages
- 1832-1857
- ISSN
- 1064-8275 (ISSN-L)
- 1095-7197
- OpenAlex
- W2022611944
- Cited by
- 280
- References
- 50
- FWCI
- 19.27
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.