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
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
Phase Retrieval via Wirtinger Flow: Theory and Algorithms
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2399924 · Cited by 1,049
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
On the use of deep learning for computational imaging
Barbastathis, G., Ozcan, A., & Situ, G. (2019) · Optica · doi:10.1364/optica.6.000921 · Cited by 869
The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
Bayati, M., & Montanari, A. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2094817 · Cited by 780
Self-citationReconNet: Non-Iterative Reconstruction of Images from Compressively Sensed Measurements
Kulkarni, K., Lohit, S., Turaga, P., Kerviche, R., & Ashok, A. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.55 · Cited by 768
Massive Connectivity With Massive MIMO—Part I: Device Activity Detection and Channel Estimation
Liu, L., & Yu, W. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2818082 · Cited by 686
Cellular, Wide-Area, and Non-Terrestrial IoT: A Survey on 5G Advances and the Road Toward 6G
Vaezi, M., Azari, A., Khosravirad, S. R., Shirvanimoghaddam, M., Azari, M. M., Chasaki, D., & Popovski, P. (2022) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2022.3151028 · Cited by 631
Federated Learning Over Wireless Fading Channels
Amiri, M. M., & Gunduz, D. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.2974748 · Cited by 625
“For this, using its knowledge of matrix A and the CSI, PS employs the approximate message passing (AMP) algorithm [29].”
MethodDeep Learning Techniques for Inverse Problems in Imaging
Ongie, G., Jalal, A., Metzler, C. A., Baraniuk, R. G., Dimakis, A. G., & Willett, R. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.2991563 · Cited by 577
Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
Mohammadi Amiri, M., & Gunduz, D. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2981904 · Cited by 548
“We use approximate message passing (AMP) algorithm to do this at the PS [31].”
MethodCommunity Detection and Stochastic Block Models
Abbe, E. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834772 · Cited by 544
Message passing algorithms for compressed sensing: I. motivation and construction
Donoho, D. L., Maleki, A., & Montanari, A. (2010) · IEEE Information Theory Workshop 2010 (ITW 2010) · doi:10.1109/itwksps.2010.5503193 · Cited by 542
Self-citationA Systematic Review of Compressive Sensing: Concepts, Implementations and Applications
Rani, M., Dhok, S. B., & Deshmukh, R. B. (2018) · IEEE Access · doi:10.1109/access.2018.2793851 · Cited by 530
Liu, L., Larsson, E. G., Yu, W., Popovski, P., Stefanovic, C., & de Carvalho, E. (2018) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2844952 · Cited by 510
Expectation-Maximization Gaussian-Mixture Approximate Message Passing
Vila, J. P., & Schniter, P. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2272287 · Cited by 501
Rank Minimization for Snapshot Compressive Imaging
Liu, Y., Yuan, X., Suo, J., Brady, D. J., & Dai, Q. (2019) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2873587 · Cited by 466
Compressive sensing: From theory to applications, a survey
Qaisar, S., Bilal, R. M., Iqbal, W., Naureen, M., & Lee, S. (2013) · Journal of Communications and Networks · doi:10.1109/jcn.2013.000083 · Cited by 457
AMP-Inspired Deep Networks for Sparse Linear Inverse Problems
Borgerding, M., Schniter, P., & Rangan, S. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2708040 · Cited by 455
Model-Driven Deep Learning for MIMO Detection
He, H., Wen, C.-K., Jin, S., & Li, G. Y. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2976585 · Cited by 454
Statistical physics of inference: thresholds and algorithms
Zdeborová, L., & Krzakala, F. (2016) · Advances in Physics · doi:10.1080/00018732.2016.1211393 · Cited by 440
Duarte, M. F., & Baraniuk, R. G. (2013) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2012.08.003 · Cited by 428
Living on the edge: phase transitions in convex programs with random data
Amelunxen, D., Lotz, M., McCoy, M. B., & Tropp, J. A. (2014) · Information and Inference · doi:10.1093/imaiai/iau005 · Cited by 413
On simplicity and complexity in the brave new world of large-scale neuroscience
Gao, P., & Ganguli, S. (2015) · Current Opinion in Neurobiology · doi:10.1016/j.conb.2015.04.003 · Cited by 405
Exploring genetic interaction manifolds constructed from rich single-cell phenotypes
Norman, T. M., Horlbeck, M. A., Replogle, J. M., Ge, A. Y., Xu, A., Jost, M., Gilbert, L. A., & Weissman, J. S. (2019) · Science · doi:10.1126/science.aax4438 · Cited by 392
Sparse Activity Detection for Massive Connectivity
Chen, Z., Sohrabi, F., & Yu, W. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2795540 · Cited by 378
Bayes-Optimal Joint Channel-and-Data Estimation for Massive MIMO With Low-Precision ADCs
Wen, C.-K., Wang, C.-J., Jin, S., Wong, K.-K., & Ting, P. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2508786 · Cited by 360
DR2-Net: Deep Residual Reconstruction Network for image compressive sensing
Yao, H., Dai, F., Zhang, S., Zhang, Y., Tian, Q., & Xu, C. (2019) · Neurocomputing · doi:10.1016/j.neucom.2019.05.006 · Cited by 356
A deep learning approach to structured signal recovery
Mousavi, A., Patel, A. B., & Baraniuk, R. G. (2015) · 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2015.7447163 · Cited by 355
Compressed Sensing for Wireless Communications: Useful Tips and Tricks
Choi, J. W., Shim, B., Ding, Y., Rao, B., & Kim, D. I. (2017) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2664421 · Cited by 351
Fast $\ell_{1}$-Minimization Algorithms for Robust Face Recognition
Yang, A. Y., Zhou, Z., Balasubramanian, A. G., Sastry, S. S., & Ma, Y. (2013) · IEEE Transactions on Image Processing · doi:10.1109/tip.2013.2262292 · Cited by 341
The Noise-Sensitivity Phase Transition in Compressed Sensing
Donoho, D. L., Maleki, A., & Montanari, A. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2165823 · Cited by 339
Self-citationLiu, H., Yuan, X., & Zhang, Y.-J. A. (2020) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2020.3007057 · Cited by 313
AMP-Net: Denoising-Based Deep Unfolding for Compressive Image Sensing
Zhang, Z., Liu, Y., Liu, J., Wen, F., & Zhu, C. (2021) · IEEE Transactions on Image Processing · doi:10.1109/tip.2020.3044472 · Cited by 311
Channel Estimation for Massive MIMO Using Gaussian-Mixture Bayesian Learning
Wen, C.-K., Jin, S., Wong, K.-K., Chen, J.-C., & Ting, P. (2015) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2014.2365813 · Cited by 310
Grant-Free Massive MTC-Enabled Massive MIMO: A Compressive Sensing Approach
Senel, K., & Larsson, E. G. (2018) · IEEE Transactions on Communications · doi:10.1109/tcomm.2018.2866559 · Cited by 296
A Model-Driven Deep Learning Network for MIMO Detection
He, H., Wen, C.-K., Jin, S., & Li, G. Y. (2018) · 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP) · doi:10.1109/globalsip.2018.8646357 · Cited by 284
Bilinear Generalized Approximate Message Passing—Part I: Derivation
Parker, J. T., Schniter, P., & Cevher, V. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2357776 · Cited by 281
On the convergence of approximate message passing with arbitrary matrices
Rangan, S., Schniter, P., & Fletcher, A. (2014) · 2014 IEEE International Symposium on Information Theory · doi:10.1109/isit.2014.6874830 · Cited by 279
Compressive Phase Retrieval via Generalized Approximate Message Passing
Schniter, P., & Rangan, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2386294 · Cited by 279
The LASSO Risk for Gaussian Matrices
Bayati, M., & Montanari, A. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2174612 · Cited by 277
Self-citationLearning to invert: Signal recovery via Deep Convolutional Networks
Mousavi, A., & Baraniuk, R. G. (2017) · 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2017.7952561 · Cited by 274
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
Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)
Maleki, A., Anitori, L., Yang, Z., & Baraniuk, R. G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2252232 · Cited by 264
Self-citationPlug-and-Play Methods for Magnetic Resonance Imaging: Using Denoisers for Image Recovery
Ahmad, R., Bouman, C. A., Buzzard, G. T., Chan, S., Liu, S., Reehorst, E. T., & Schniter, P. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2019.2949470 · Cited by 261
Ganguli, S., & Sompolinsky, H. (2012) · Annual Review of Neuroscience · doi:10.1146/annurev-neuro-062111-150410 · Cited by 256
Deep Learning for Distributed Channel Feedback and Multiuser Precoding in FDD Massive MIMO
Sohrabi, F., Attiah, K. M., & Yu, W. (2021) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2021.3055202 · Cited by 169
Compressed Sensing With Approximate Message Passing Using In-Memory Computing
Le Gallo, M., Sebastian, A., Cherubini, G., Giefers, H., & Eleftheriou, E. (2018) · IEEE Transactions on Electron Devices · doi:10.1109/ted.2018.2865352 · Cited by 99
“noise is generally not Gaussian, and state evolution does not hold [6], [7].”
BackgroundMethodCompressed sensing recovery using computational memory
Le Gallo, M., Sebastian, A., Cherubini, G., Giefers, H., & Eleftheriou, E. (2017) · 2017 IEEE International Electron Devices Meeting (IEDM) · doi:10.1109/iedm.2017.8268469 · Cited by 28
Harnessing wireless channels for scalable and privacy-preserving federated learning
Elgabli, A., Park, J., Issaid, C. B., & Bennis, M. (2021) · IEEE Transactions on Communications · doi:10.1109/tcomm.2021.3078783 · Cited by 14
Sparse recovery of time-frequency representations via recurrent neural networks
Khalifa, Y., Zhang, Z., & Sejdic, E. (2017) · 2017 22nd International Conference on Digital Signal Processing (DSP) · doi:10.1109/icdsp.2017.8096132 · Cited by 5
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.