The DOI matches its Crossref record; 58 of the 58 references it cites were found in a registry or an index.
Just relax: convex programming methods for identifying sparse signals in noise
Abstract
This paper studies a difficult and fundamental problem that arises throughout electrical engineering, applied mathematics, and statistics. Suppose that one forms a short linear combination of elementary signals drawn from a large, fixed collection. Given an observation of the linear combination that has been contaminated with additive noise, the goal is to identify which elementary signals participated and to approximate their coefficients. Although many algorithms have been proposed, there is little theory which guarantees that these algorithms can accurately and efficiently solve the problem. This paper studies a method called convex relaxation, which attempts to recover the ideal sparse signal by solving a convex program. This approach is powerful because the optimization can be completed in polynomial time with standard scientific software. The paper provides general conditions which ensure that convex relaxation succeeds. As evidence of the broad impact of these results, the paper describes how convex relaxation can be used for several concrete signal recovery problems. It also describes applications to channel coding, linear regression, and numerical analysis
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
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
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Regularization and Variable Selection Via the Elastic Net
Zou, H., & Hastie, T. (2005) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00503.x · Cited by 20,957
A Wavelet Tour of Signal Processing
(1999) · Elsevier eBooks · doi:10.1016/b978-0-12-466606-1.x5000-4 · Cited by 16,227
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Horn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280
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
Golub, G. H., & Loan, C. F. V. (1996) · Johns Hopkins University Press eBooks · Cited by 6,027
Modeling by shortest data description
Rissanen, J. (1978) · Automatica · doi:10.1016/0005-1098(78)90005-5 · Cited by 6,011
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Emergence of simple-cell receptive field properties by learning a sparse code for natural images
Olshausen, B. A., & Field, D. J. (1996) · Nature · doi:10.1038/381607a0 · Cited by 5,694
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
Pati, Y. C., Rezaiifar, R., & Krishnaprasad, P. S. (2002) · Proceedings of 27th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.1993.342465 · Cited by 4,323
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
Self-citationGoemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Combinatorial optimization:Algorithms and complexity
Rabiner, L. (1984) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1984.1164450 · Cited by 3,576
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
Donoho, D. L., & Elad, M. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0437847100 · Cited by 2,898
Introductory functional analysis with applications
Kreyszig, E. (1978) · Cited by 2,889
Sparse Approximate Solutions to Linear Systems
Natarajan, B. K. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792240406 · Cited by 2,783
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
Stable 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
Uncertainty principles and ideal atomic decomposition
Donoho, D. L., & Huo, X. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.959265 · Cited by 1,949
Clustering with Bregman Divergences
Banerjee, A., Merugu, S., Dhillon, I., & Ghosh, J. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.22 · Cited by 1,472
Sparse solutions to linear inverse problems with multiple measurement vectors
Cotter, S. F., Rao, B. D., Engan, K., & Kreutz-Delgado, K. (2005) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2005.849172 · Cited by 1,393
Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit
Tropp, J. A., Gilbert, A. C., & Strauss, M. J. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.030 · Cited by 1,347
Self-citationAdaptive greedy approximations
Davis, G., Mallat, S., & Avellaneda, M. (1997) · Constructive Approximation · doi:10.1007/bf02678430 · Cited by 1,166
Minimax estimation via wavelet shrinkage
Donoho, D. L., & Johnstone, I. M. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691081 · Cited by 1,005
Sparse representations in unions of bases
Gribonval, R., & Nielsen, M. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.820031 · Cited by 960
Subset Selection in Regression
Miller, A. (2002) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420035933 · Cited by 929
Robust Modeling With Erratic Data
Claerbout, J. F., & Muir, F. (1973) · Geophysics · doi:10.1190/1.1440378 · Cited by 833
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
Algorithms for simultaneous sparse approximation. Part II: Convex relaxation
Tropp, J. A. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.031 · Cited by 691
Self-citationA generalized uncertainty principle and sparse representation in pairs of bases
Elad, M., & Bruckstein, A. M. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.801410 · Cited by 673
Subset Selection in Regression
Miller, A. J. (1990) · Springer eBooks · doi:10.1007/978-1-4899-2939-6 · Cited by 625
Parallel Preconditioning with Sparse Approximate Inverses
Grote, M. J., & Huckle, T. (1997) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827594276552 · Cited by 600
On Sparse Representations in Arbitrary Redundant Bases
Fuchs, J.-J. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.828141 · Cited by 563
An affine scaling methodology for best basis selection
Rao, B. D., & Kreutz-Delgado, K. (1999) · IEEE Transactions on Signal Processing · doi:10.1109/78.738251 · Cited by 526
An Equivalence Between Sparse Approximation and Support Vector Machines
Girosi, F. (1998) · Neural Computation · doi:10.1162/089976698300017269 · Cited by 506
Quantitative 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
Combinatorial optimization: algorithms and complexity
Papadimitriou, C. H., & Steiglitz, K. (1998) · CERN Document Server (European Organization for Nuclear Research) · Cited by 486
An Elementary Introduction to Modern Convex Geometry
Ball, K. (1997) · Cambridge University Press eBooks · doi:10.1017/9781009701853.002 · Cited by 483
Recovery of the acoustic impedance from reflection seismograms
Oldenburg, D. W., Scheuer, T., & Levy, S. (1983) · Geophysics · doi:10.1190/1.1441413 · Cited by 480
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
ALGORITHMS FOR SIMULTANEOUS SPARSE APPROXIMATIONPreprint
Tropp, J. A. (2006) · Cited by 350
Self-citationRecovery of Exact Sparse Representations in the Presence of Bounded Noise
Fuchs, J. J. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.855614 · Cited by 314
Nonlinear Methods of Approximation
Temlyakov, V. N. (2003) · Foundations of Computational Mathematics · doi:10.1007/s102080010029 · Cited by 309
Levy, S., & Fullagar, P. K. (1981) · Geophysics · doi:10.1190/1.1441261 · Cited by 258
Harmonic decomposition of audio signals with matching pursuit
Gribonval, R., & Bacry, E. (2003) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2002.806592 · Cited by 239
On the application of the global matched filter to DOA estimation with uniform circular arrays
Fuchs, J.-J. (2001) · IEEE Transactions on Signal Processing · doi:10.1109/78.912914 · Cited by 195
On sparse representation in pairs of bases
Feuer, A., & Nemirovski, A. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.811926 · Cited by 158
Just relax: Convex programming methods for subset selection and sparse approximation
Tropp, J. A. (2004) · Cited by 113
Self-citationConvex Geometry and Functional Analysis
Ball, K. (2001) · Handbook of the geometry of Banach spaces · doi:10.1016/s1874-5849(01)80006-1 · Cited by 90
Simultaneous approximation by greedy algorithms
Leviatan, D., & Temlyakov, V. N. (2006) · Advances in Computational Mathematics · doi:10.1007/s10444-004-7613-4 · Cited by 63
Applications of sparse approximation in communications
Gilbert, A. C., & Tropp, J. A. (2005) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2005.1523488 · Cited by 25
Self-citation
Cited by
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
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
Enhancing Sparsity by Reweighted ℓ 1 Minimization
Candès, E. J., Wakin, M. B., & Boyd, S. P. (2008) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9045-x · Cited by 4,863
Nearly unbiased variable selection under minimax concave penalty
Zhang, C.-H. (2010) · The Annals of Statistics · doi:10.1214/09-aos729 · Cited by 3,835
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
Metadata
- Authors
- Tropp, J. A.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2006-03
- Volume
- 52
- Issue
- 3
- Pages
- 1030-1051
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2147656689
- Cited by
- 1,407
- References
- 58
- FWCI
- 84.53
- 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.