The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
Abstract
This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with$m$nonzero entries in dimension$d$given$ {\rm O}(m \ln d)$random linear measurements of that signal. This is a massive improvement over previous results, which require${\rm O}(m^{2})$measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.
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
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
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
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
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
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
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
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (2001) · SIAM Review · doi:10.1137/s003614450037906x · Cited by 5,085
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
Interior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y., & Nemirovskii, A. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,334
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-citationFigueiredo, 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
Numerical Methods for Least Squares Problems
Björck, Å. (1996) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971484 · Cited by 3,257
Numerical methods for least squares problems
(1996) · Choice Reviews Online · doi:10.5860/choice.34-1602 · Cited by 3,007
SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
Gill, P. E., Murray, W., & Saunders, M. A. (2005) · SIAM Review · doi:10.1137/s0036144504446096 · Cited by 2,834
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
A Simple Proof of the Restricted Isometry Property for Random Matrices
Baraniuk, R., Davenport, M., DeVore, R., & Wakin, M. (2008) · Constructive Approximation · doi:10.1007/s00365-007-9003-x · Cited by 2,372
Friedman, J. H., & Stuetzle, W. (1981) · Journal of the American Statistical Association · doi:10.1080/01621459.1981.10477729 · Cited by 2,216
The Concentration of Measure Phenomenon
Ledoux, M. (2005) · Mathematical Surveys and Monographs · doi:10.1090/surv/089 · Cited by 1,700
Subset Selection in Regression
(2003) · Technometrics · doi:10.1198/tech.2003.s144 · Cited by 1,463
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
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
Ledoux, M., & Talagrand, M. (1991) · doi:10.1007/978-3-642-20212-4 · Cited by 1,160
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit
Needell, D., & Vershynin, R. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-008-9031-3 · Cited by 952
Subset Selection in Regression
Miller, A. (2002) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420035933 · Cited by 929
DeVore, R. A. (1998) · Acta Numerica · doi:10.1017/s0962492900002816 · Cited by 877
Matrix Computations, 3rd Edition
Golub, G. H. (2007) · Cited by 787
Combinatorial Group Testing and Its Applications
Du, D.-Z., & Hwang, F. K. (1999) · Series on Applied Mathematics · doi:10.1142/9789812798107 · Cited by 773
Some remarks on greedy algorithms
DeVore, R., & Temlyakov, V. N. (1996) · Advances in Computational Mathematics · doi:10.1007/bf02124742 · Cited by 646
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
Local Operator Theory, Random Matrices and Banach Spaces
(2001) · Handbook of the Geometry of Banach Spaces · doi:10.1016/s1874-5849(01)80010-3 · Cited by 432
Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit
Donoho, D. L., Tsaig, Y., Drori, I., & Starck, J. (2006) · Cited by 419
Regularite des trajectoires des fonctions aleatoires gaussiennes
Fernique, X. (1975) · Lecture notes in mathematics · doi:10.1007/bfb0080190 · Cited by 404
ALGORITHMS FOR SIMULTANEOUS SPARSE APPROXIMATIONPreprint
Tropp, J. A. (2006) · Cited by 350
Self-citationNonlinear Methods of Approximation
Temlyakov, V. N. (2003) · Foundations of Computational Mathematics · doi:10.1007/s102080010029 · Cited by 309
On the probability that a random ±1-matrix is singular
Kahn, J., Komlós, J., & Szemerédi, E. (1995) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-1995-1260107-2 · Cited by 158
Convex 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
The Johnson-Lindenstrauss Lemma Meets Compressed Sensing
Baraniuk, R. G., Davenport, M. A., DeVore, R., & Wakin, M. B. (2006) · Cited by 56
Research works printed but not linked: 8
- fernique, 1974, Ecole D'Et� de Probabilit�s de Saint-Flour IV, 480, 1
- 10.1109/ICASSP.2005.1416408 · DOI
- kim, 2007, ?A method for large-scale -regularized least-squares problems with applications in signal processing and statistics ?
- lugosi, 2005, Concentration of Measure Inequalities
- ball, 2002, Handbook of Banach Space Geometry, 161
- 10.1155/IMRN.2005.4019 · doi:10.1155/imrn.2005.4019
- 10.1007/s10208-007-9005-x · doi:10.1007/s10208-007-9005-x
- tropp, 2007, ?Signal recovery from random measurements via orthogonal matching pursuit The Gaussian case ?
Cited by
An Introduction To Compressive Sampling
Candes, E. J., & Wakin, M. B. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914731 · Cited by 10,017
Discovering governing equations from data by sparse identification of nonlinear dynamical systems
Brunton, S. L., Proctor, J. L., & Kutz, J. N. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1517384113 · Cited by 4,796
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
Self-citationSpatially Sparse Precoding in Millimeter Wave MIMO Systems
Ayach, O. E., Rajagopal, S., Abu-Surra, S., Pi, Z., & Heath, R. W. (2014) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2014.011714.130846 · Cited by 3,557
Recent advances and applications of machine learning in solid-state materials science
Schmidt, J., Marques, M. R. G., Botti, S., & Marques, M. A. L. (2019) · npj Computational Materials · doi:10.1038/s41524-019-0221-0 · Cited by 2,607
Metadata
- Authors
- Tropp, J. A., & Gilbert, A. C.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2007-12
- Volume
- 53
- Issue
- 12
- Pages
- 4655-4666
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2127271355
- Cited by
- 9,653
- References
- 42
- FWCI
- 198.70
- 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.