The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
The Noise-Sensitivity Phase Transition in Compressed Sensing
Abstract
Consider the noisy underdetermined system of linear equations: y = Ax0+ z, with A an n × N measurement matrix, n2I) a Gaussian white noise. Both y and A are known, both x0and z are unknown, and we seek an approximation to x0. When x0has few nonzeros, useful approximations are often obtained by ℓ1-penalized ℓ2minimization, in which the reconstruction x̂1,λsolves min{||y - Ax||22/2 + λ||x||1}. Consider the reconstruction mean-squared error MSE = E|| x̂1,λ- x0||22/N, and define the ratio MSE/σ2as the noise sensitivity. Consider matrices A with i.i.d. Gaussian entries and a large-system limit in which n, N → ∞ with n/N → δ and k/n → ρ. We develop exact expressions for the asymptotic MSE of x̂1,λ, and evaluate its worst-case noise sensitivity over all types of k-sparse signals. The phase space 0 ≤ 8, ρ ≤ 1 is partitioned by the curve ρ = ρMSE(δ) into two regions. Formal noise sensitivity is bounded throughout the region ρ = ρMSE(δ) and is unbounded throughout the region ρ = ρMSE(δ). The phase boundary ρ = ρMSE(δ) is identical to the previously known phase transition curve for equivalence of ℓ1- ℓ0minimization in the k-sparse noiseless case. Hence, a single phase boundary describes the fundamental phase transitions both for the noise less and noisy cases. Extensive computational experiments validate these predictions, including the existence of game-theoretical structures underlying it (saddlepoints in the payoff, least-favorable signals and maximin penalization). Underlying our formalism is an approximate message passing soft thresholding algorithm (AMP) introduced earlier by the authors. Other papers by the authors detail expressions for the formal MSE of AMP and its close connection to ℓ1-penalized reconstruction. The focus of the present paper is on computing the minimax formal MSE within the class of sparse signals x0.
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
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
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952
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
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
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-citationFactor graphs and the sum-product algorithm
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486 · cited 1×
“The underlying factor graph [23] is the complete bipartite graph over variable nodes and factor nodes.”
BackgroundAn 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
Message-passing algorithms for compressed sensing
Donoho, D. L., Maleki, A., & Montanari, A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0909892106 · Cited by 2,416
Self-citationRichardson, T., & Urbanke, R. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511791338 · Cited by 2,271
Information, Physics, and Computation
Mézard, M., & Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,913
Self-citationThe Dantzig selector: Statistical estimation when p is much larger than n
Candes, E., & Tao, T. (2007) · The Annals of Statistics · doi:10.1214/009053606000001523 · Cited by 1,747
Constructing 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
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
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-citationMessage 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-citationDonoho, 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-citationSpin Glasses: A Challenge for Mathematicians
Talagrand, M. (2003) · Cited by 324
A 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
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-citationMinimax 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-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
A typical reconstruction limit for compressed sensing based on Lp-norm minimization
Kabashima, Y., Wadayama, T., & Tanaka, T. (2009) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2009/09/l09003 · Cited by 177
Compressed Sensing: How Sharp Is the Restricted Isometry Property?
Blanchard, J. D., Cartis, C., & Tanner, J. (2011) · SIAM Review · doi:10.1137/090748160 · Cited by 160
Maxwell Construction: The Hidden Bridge Between Iterative and Maximuma PosterioriDecoding
Méasson, C., Andrea Montanari, A., & Urbanke, R. L. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.2006466 · Cited by 127
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
Chen, S., & Donoho, D. L. (1995) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.217610 · Cited by 49
Self-citationImproved message passing for inference in densely connected systems
Neirotti, J. P., & Saad, D. (2005) · Europhysics Letters (EPL) · doi:10.1209/epl/i2005-10148-5 · Cited by 44
From Naive Mean Field Theory to the TAP Equations
Opper, M., & Winther, O. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/1100.003.0006 · Cited by 34
Cited by
(2015) · Cited by 2,857
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-citationA Probabilistic and RIPless Theory of Compressed Sensing
Candes, E. J., & Plan, Y. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2161794 · Cited by 598
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
Metadata
- Authors
- Donoho, D. L., Maleki, A., & Montanari, A.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2011-10
- Volume
- 57
- Issue
- 10
- Pages
- 6920-6941
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2164595191
- Cited by
- 339
- References
- 30
- FWCI
- 41.94
- 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.