The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index.
Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
Abstract
Finding the sparsest solution to underdetermined systems of linear equationsy= Φxis NP-hard in general. We show here that for systems with “typical”/“random” Φ, a good approximation to the sparsest solution is obtained by applying a fixed number of standard operations from linear algebra. Our proposal, Stagewise Orthogonal Matching Pursuit (StOMP), successively transforms the signal into a negligible residual. Starting with initial residualr0=y, at thes-th stage it forms the “matched filter” ΦTrs-1, identifies all coordinates with amplitudes exceeding a specially chosen threshold, solves a least-squares problem using the selected coordinates, and subtracts the least-squares fit, producing a new residual. After a fixed number of stages (e.g., 10), it stops. In contrast to Orthogonal Matching Pursuit (OMP), many coefficients can enter the model at each stage in StOMP while only one enters per stage in OMP; and StOMP takes a fixed number of stages (e.g., 10), while OMP can take many (e.g.,n). We give both theoretical and empirical support for the large-system effectiveness of StOMP. We give numerical examples showing that StOMP rapidly and reliably finds sparse solutions in compressed sensing, decoding of error-correcting codes, and overcomplete representation.
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
Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing
Benjamini, Y., & Hochberg, Y. (1995) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1995.tb02031.x · Cited by 109,482
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
Self-citationDonoho, D. L. (2004) · Cited by 16,703
Self-citationCandes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
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
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
Ideal spatial adaptation by wavelet shrinkage
Donoho, D. L., & Johnstone, I. M. (1994) · Biometrika · doi:10.1093/biomet/81.3.425 · Cited by 8,760
Self-citationDecoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
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
Self-citationNear-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
Testing Statistical Hypotheses
(2021) · Wiley Series in Probability and Statistics · doi:10.1002/9781119243830.ch12 · Cited by 5,106
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
Verdú, S. (1998) · Cited by 4,711
Adapting to Unknown Smoothness via Wavelet Shrinkage
Donoho, D. L., & Johnstone, I. M. (1995) · Journal of the American Statistical Association · doi:10.1080/01621459.1995.10476626 · Cited by 4,630
Self-citationGreed 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
Introduction to Space-Time Wireless Communications
Paulraj, A. J., Nabar, R. U., & Gore, D. (2003) · Cited by 3,469
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
Self-citationDonoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
Self-citationMultiple Comparison Procedures
Hochberg, Y., & Tamhane, A. C. (1987) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316672 · Cited by 2,389
Multiple Comparison Procedures
(2013) · An Introduction to Statistical Concepts · doi:10.4324/9780203137819-17 · Cited by 2,109
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
Self-citationOn the inherent intractability of certain coding problems (Corresp.)
Berlekamp, E., McEliece, R., & van Tilborg, H. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055873 · Cited by 1,523
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
Image decomposition via the combination of sparse representations and a variational approach
Starck, J.-L., Elad, M., & Donoho, D. L. (2005) · IEEE Transactions on Image Processing · doi:10.1109/tip.2005.852206 · Cited by 987
Self-citationSparse representations in unions of bases
Gribonval, R., & Nielsen, M. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.820031 · Cited by 960
Extensions of compressed sensing
Tsaig, Y., & Donoho, D. L. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.029 · Cited by 947
Self-citationSpectral efficiency of CDMA with random spreading
Verdu, S., & Shamai, S. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.749007 · Cited by 885
(1995) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-2544-7 · Cited by 569
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
WaveLab and Reproducible Research
Buckheit, J. B., & Donoho, D. L. (1995) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-2544-7_5 · Cited by 537
Self-citationNeedles and straw in haystacks: Empirical Bayes estimates of possibly sparse sequences
Johnstone, I. M., & Silverman, B. W. (2004) · The Annals of Statistics · doi:10.1214/009053604000000030 · Cited by 456
Adapting to unknown sparsity by controlling the false discovery rate
Abramovich, F., Benjamini, Y., Donoho, D. L., & Johnstone, I. M. (2006) · The Annals of Statistics · doi:10.1214/009053606000000074 · Cited by 455
Self-citationRedundant Multiscale Transforms and Their Application for Morphological Component Separation
Starck, J.-L., Elad, M., & Donoho, D. (2004) · Advances in Imaging and Electron Physics · doi:10.1016/s1076-5670(04)32006-9 · Cited by 443
Self-citationMaximum Entropy and the Nearly Black Object
Donoho, D. L., Johnstone, I. M., Hoch, J. C., & Stern, A. S. (1992) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1992.tb01864.x · Cited by 393
Self-citationHigh-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension
Donoho, D. L. (2006) · Discrete & Computational Geometry · doi:10.1007/s00454-005-1220-0 · Cited by 370
Self-citationIterative multiuser joint decoding: unified framework and asymptotic analysis
Boutros, J., & Caire, G. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.1013125 · Cited by 314
Nonlinear Methods of Approximation
Temlyakov, V. N. (2003) · Foundations of Computational Mathematics · doi:10.1007/s102080010029 · Cited by 290
Near-optimal sparse fourier representations via sampling
Gilbert, A. C., Guha, S., Indyk, P., Muthukrishnan, S., & Strauss, M. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509933 · Cited by 259
Breakdown of equivalence between the minimalℓ1-norm solution and the sparsest solution
Tsaig, Y., & Donoho, D. L. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.028 · Cited by 241
Self-citationRovnyak, D., Frueh, D. P., Sastry, M., Sun, Z.-Y. J., Stern, A. S., Hoch, J. C., & Wagner, G. (2004) · Journal of Magnetic Resonance · doi:10.1016/j.jmr.2004.05.016 · Cited by 239
Minimax risk overl p -balls forl p -error
Donoho, D. L., & Johnstone, I. M. (1994) · Probability Theory and Related Fields · doi:10.1007/bf01199026 · Cited by 218
Self-citationNew methods for fast multidimensional NMR
Freeman, R., & Kupče, E. (2003) · Journal of Biomolecular NMR · doi:10.1023/a:1024960302926 · Cited by 185
Testing Statistical Hypotheses
Ziegel, E. (1987) · Technometrics · doi:10.1080/00401706.1987.10488294 · Cited by 183
Iterative Multiuser Joint Decoding: Optimal Power Allocation and Low-Complexity Implementation
Caire, G., Muller, R. R., & Tanaka, T. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.833351 · Cited by 175
Output MAI distributions of linear MMSE multiuser receivers in DS-CDMA systems
Zhang, J., Chong, E. K. P., & Tse, D. N. C. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.915669 · Cited by 172
Signal Recovery and the Large Sieve
Donoho, D. L., & Logan, B. F. (1992) · SIAM Journal on Applied Mathematics · doi:10.1137/0152031 · Cited by 166
Self-citationDifferent Perspectives on Wavelets
Daubechies, I. C. (1993) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/047 · Cited by 94
Greedy Algorithms andM-Term Approximation with Regard to Redundant Dictionaries
Temlyakov, V. N. (1999) · Journal of Approximation Theory · doi:10.1006/jath.1998.3265 · Cited by 86
Asymptotic minimaxity of false discovery rate thresholding for sparse exponential data
Donoho, D. L., & Jin, J. (2006) · The Annals of Statistics · doi:10.1214/009053606000000920 · Cited by 55
Self-citationBEAMLAB AND REPRODUCIBLE RESEARCH
Donoho, D. L., & Huo, X. (2004) · International Journal of Wavelets Multiresolution and Information Processing · doi:10.1142/s0219691304000615 · Cited by 29
Self-citation
Cited by
Applications of Deep Reinforcement Learning in Communications and Networking: A Survey
Luong, N. C., Hoang, D. T., Gong, S., Niyato, D., Wang, P., Liang, Y.-C., & Kim, D. I. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2916583 · Cited by 2,060
Model-Based Compressive Sensing
Baraniuk, R. G., Cevher, V., Duarte, M. F., & Hegde, C. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2040894 · Cited by 1,308
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
Solving inverse problems using data-driven models
Arridge, S., Maass, P., Öktem, O., & Schönlieb, C.-B. (2019) · Acta Numerica · doi:10.1017/s0962492919000059 · Cited by 686
A Review of Sparse Recovery Algorithms
Crespo Marques, E., Maciel, N., Naviner, L., Cai, H., & Yang, J. (2019) · IEEE Access · doi:10.1109/access.2018.2886471 · Cited by 268
Metadata
- Authors
- Donoho, D. L., Tsaig, Y., Drori, I., & Starck, J.-L.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2012-02
- Volume
- 58
- Issue
- 2
- Pages
- 1094-1121
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2046658845
- Cited by
- 1,509
- References
- 51
- FWCI
- 122.32
- 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.