The DOI matches its Crossref record; 56 of the 56 references it cites were found in a registry or an index.
Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems
Abstract
Many problems in signal processing and statistical inference involve finding sparse solutions to under-determined, or ill-conditioned, linear systems of equations. A standard approach consists in minimizing an objective function which includes a quadratic (squared ) error term combined with a sparseness-inducing regularization term. Basis pursuit, the least absolute shrinkage and selection operator (LASSO), wavelet-based deconvolution, and compressed sensing are a few well-known examples of this approach. This paper proposes gradient projection (GP) algorithms for the bound-constrained quadratic programming (BCQP) formulation of these problems. We test variants of this approach that select the line search parameters in different ways, including techniques based on the Barzilai-Borwein method. Computational experiments show that these GP approaches perform well in a wide range of applications, often being significantly faster (in terms of computation time) than competing methods. Although the performance of GP methods tends to degrade as the regularization term is de-emphasized, we show how they can be embedded in a continuation scheme to recover their efficient practical performance.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
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
A Wavelet Tour of Signal Processing
(1999) · Elsevier eBooks · doi:10.1016/b978-0-12-466606-1.x5000-4 · Cited by 16,227
Nonlinear total variation based noise removal algorithms
Rudin, L. I., Osher, S., & Fatemi, E. (1992) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(92)90242-f · Cited by 15,704
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Advances in Neural Information Processing Systems 19
(2007) · The MIT Press eBooks · doi:10.52202/085713 · Cited by 15,539
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
De-noising by soft-thresholding
Donoho, D. L. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382009 · Cited by 9,619
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
(2006) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/978-0-387-40065-5 · Cited by 9,008
Stable signal recovery from incomplete and inaccurate measurements
Candès, E. J., Romberg, J. K., & Tao, T. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20124 · Cited by 7,036
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
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
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
LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
Paige, C. C., & Saunders, M. A. (1982) · ACM Transactions on Mathematical Software · doi:10.1145/355984.355989 · Cited by 4,387
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
Regression Shrinkage and Selection via The Lasso: A Retrospective
Tibshirani, R. (2011) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2011.00771.x · Cited by 3,589
chambolle (2004) · doi:10.1023/b:jmiv.0000011321.19549.88 · Cited by 3,227
An algorithm for quadratic programming
Frank, M., & Wolfe, P. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030109 · Cited by 3,030
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
The Linear Complementarity Problem
Cottle, R. W., Pang, J.-S., & Stone, R. E. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719000 · Cited by 2,788
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
Weik, M. H. (2000) · Computer Science and Communications Dictionary · doi:10.1007/1-4020-0613-6_12436 · Cited by 2,570
Primal-Dual Interior-Point Methods
Wright, S. J. (1997) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971453 · Cited by 2,391
Self-citationStable recovery of sparse overcomplete representations in the presence of noise
Donoho, D. L., Elad, M., & Temlyakov, V. N. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.860430 · Cited by 2,183
Hunter, D. R., & Lange, K. (2004) · The American Statistician · doi:10.1198/0003130042836 · Cited by 1,783
The Dantzig selector: Statistical estimation when p is much larger than n
Candes, E., & Tao, T. (2007) · The Annals of Statistics · doi:10.1214/009053606000001523 · Cited by 1,747
Subset Selection in Regression
(2003) · Technometrics · doi:10.1198/tech.2003.s144 · Cited by 1,463
Just 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
Self-citationAdaptive greedy approximations
Davis, G., Mallat, S., & Avellaneda, M. (1997) · Constructive Approximation · doi:10.1007/bf02678430 · Cited by 1,166
Nonmonotone Spectral Projected Gradient Methods on Convex Sets
Birgin, E. G., Martínez, J. M., & Raydan, M. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497330963 · Cited by 1,056
Subset Selection in Regression
Miller, A. (2002) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420035933 · Cited by 929
A new approach to variable selection in least squares problems
Osborne, M. (2000) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/20.3.389 · Cited by 859
Robust Modeling With Erratic Data
Claerbout, J. F., & Muir, F. (1973) · Geophysics · doi:10.1190/1.1440378 · Cited by 833
Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
Donoho, D. L., & Tsaig, Y. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.929958 · Cited by 829
Linear Inversion of Band-Limited Reflection Seismograms
Santosa, F., & Symes, W. W. (1986) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0907087 · Cited by 713
Signal Reconstruction From Noisy Random Projections
Haupt, J., & Nowak, R. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.880031 · Cited by 608
Self-citationOn Sparse Representations in Arbitrary Redundant Bases
Fuchs, J.-J. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.828141 · Cited by 563
Blumensath, T., & Davies, M. E. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.916124 · Cited by 461
Deconvolution with the l 1 norm
Taylor, H. L., Banks, S. C., & McCoy, J. F. (1979) · Geophysics · doi:10.1190/1.1440921 · Cited by 436
Simultaneous Variable Selection
Turlach, B. A., Venables, W. N., & Wright, S. J. (2005) · Technometrics · doi:10.1198/004017005000000139 · Cited by 386
Self-citationOn 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
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
Levy, S., & Fullagar, P. K. (1981) · Geophysics · doi:10.1190/1.1441261 · Cited by 258
Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms
Moghaddam, B., Weiss, Y., & Avidan, S. (2005) · Cited by 207
A bound optimization approach to wavelet-based image deconvolution
Figueiredo, M. A. T., & Nowak, R. D. (2005) · IEEE International Conference on Image Processing 2005 · doi:10.1109/icip.2005.1530172 · Cited by 189
Self-citationSerafini, T., Zanghirati, G., & Zanni, L. (2005) · Optimization methods & software · doi:10.1080/10556780512331318182 · Cited by 130
Multipath time-delay detection and estimation
Fuchs, J.-J. (1999) · IEEE Transactions on Signal Processing · doi:10.1109/78.738263 · Cited by 107
Image Denoising with Shrinkage and Redundant Representations
Elad, M., Matalon, B., & Zibulevsky, M. (2006) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2006.143 · Cited by 91
Fast 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
Self-citationMore on sparse representations in arbitrary bases
Fuchs, J. J. (2003) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)34942-x · Cited by 46
Cited by
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
Tropp, J. A., & Gilbert, A. C. (2007) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.909108 · Cited by 9,653
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
Metadata
- Authors
- Figueiredo, M. A. T., Nowak, R. D., & Wright, S. J.
- Venue
- IEEE Journal of Selected Topics in Signal Processing
- Published
- 2007-12
- Volume
- 1
- Issue
- 4
- Pages
- 586-597
- ISSN
- 1932-4553 (ISSN-L)
- 1941-0484
- OpenAlex
- W2109449402
- Cited by
- 3,524
- References
- 56
- FWCI
- 156.42
- 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.