The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Message-passing algorithms for compressed sensing
Open accessAbstract
Compressed sensing aims to undersample certain high-dimensional signals yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity–undersampling tradeoff is achieved when reconstructing by convex optimization, which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity–undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity–undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity–undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity–undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this apparently very different theoretical formalism.
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. (2004) · Cited by 16,703
Self-citation(1988) · Cited by 16,582
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Low-density parity-check codes
Gallager, R. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057683 · Cited by 10,602
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
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
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-citationAn 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
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
Subspace Pursuit for Compressive Sensing Signal Reconstruction
Dai, W., & Milenkovic, O. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2016006 · Cited by 2,388
Richardson, T., & Urbanke, R. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511791338 · Cited by 2,271
Lustig, M., Donoho, D. L., Santos, J. M., & Pauly, J. M. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914728 · Cited by 2,246
Self-citationConstructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850085 · Cited by 1,617
(1988) · doi:10.1016/b978-0-08-051489-5.50008-4 · Cited by 1,429
Solution of 'Solvable model of a spin glass'
Thouless, D. J., Anderson, P. W., & Palmer, R. G. (1977) · Philosophical Magazine · doi:10.1080/14786437708235992 · Cited by 1,286
Computational 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
MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.856938 · Cited by 654
Bayesian Compressive Sensing Via Belief Propagation
Baron, D., Sarvotham, S., & Baraniuk, R. G. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2027773 · Cited by 498
Donoho, D., & Tanner, J. (2009) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2009.0152 · Cited by 436
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-citationA CDMA multiuser detection algorithm on the basis of belief propagation
Kabashima, Y. (2003) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/36/43/030 · Cited by 324
Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing
Maleki, A., & Donoho, D. L. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2009.2039176 · Cited by 289
Self-citationMax-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
Bayati, M., Shah, D., & Sharma, M. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.915695 · Cited by 224
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-citationCounter braids: a novel counter architecture for per-flow measurement
Lu, Y., Montanari, A., Prabhakar, B., Dharmapurikar, S., & Kabbani, A. (2008) · Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/1375457.1375472 · Cited by 206
Self-citationAsymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
Rangan, S., Fletcher, A. K., & Goyal, V. K. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2177575 · Cited by 189
Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications
Donoho, D. L., & Tanner, J. (2010) · Discrete & Computational Geometry · doi:10.1007/s00454-009-9221-z · Cited by 183
Self-citationComputational Methods for Sparse Solution of Linear Inverse Problems
Tropp, J. A., & Wright, S. J. (2009) · Defense Technical Information Center (DTIC) · doi:10.21236/ada633835 · Cited by 144
Message passing algorithms for compressed sensing: II. analysis and validation
Donoho, D. L., Maleki, A., & Andrea Montanari, A. (2010) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itwksps.2010.5503228 · Cited by 135
Self-citationIEEE Signal Processing Magazine
(2009) · IEEE Signal Processing Magazine · doi:10.1109/msp.2009.5174485 · Cited by 133
A single-letter characterization of optimal noisy compressed sensing
Guo, D., Baron, D., & Shamai, S. S. (2009) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2009.5394838 · Cited by 113
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
Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing
Monga, V., Li, Y., & Eldar, Y. C. (2021) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3016905 · Cited by 1,414
Deep Learning for Massive MIMO CSI Feedback
Wen, C.-K., Shih, W.-T., & Jin, S. (2018) · IEEE Wireless Communications Letters · doi:10.1109/lwc.2018.2818160 · Cited by 1,174
A Survey of Sparse Representation: Algorithms and Applications
Zhang, Z., Xu, Y., Yang, J., Li, X., & Zhang, D. (2015) · IEEE Access · doi:10.1109/access.2015.2430359 · Cited by 1,092
Metadata
- Authors
- Donoho, D. L., Maleki, A., & Montanari, A.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2009-11-10
- Volume
- 106
- Issue
- 45
- Pages
- 18914-18919
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2082029531
- Cited by
- 2,416
- References
- 32
- FWCI
- 69.14
- Type
- journal article
- Language
- en
- Open access
- green
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.