Living on the edge: phase transitions in convex programs with random data
Open accessThe DOI matches its Crossref record; 59 of the 59 references it cites were found in a registry or an index.
Abstract
Recent research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the ℓ1 minimization method for identifying a sparse vector from random linear measurements. Indeed, the ℓ1 approach succeeds with high probability when the number of measurements exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability. This paper provides the first rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. It also describes tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region. These techniques apply to regularized linear inverse problems with random measurements, to demixing problems under a random incoherence model, and also to cone programs with random affine constraints. The applied results depend on foundational research in conic geometry. This paper introduces a summary parameter, called the statistical dimension, that canonically extends the dimension of a linear subspace to the class of convex cones. The main technical result demonstrates that the sequence of intrinsic volumes of a convex cone concentrates sharply around the statistical dimension. This fact leads to accurate bounds on the probability that a randomly rotated cone shares a ray with a fixed cone.
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
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables
W., J. W., Abramowitz, M., & Stegun, I. A. (1965) · Mathematics of Computation · doi:10.2307/2004114 · Cited by 18,663
Donoho, D. L. (2004) · Cited by 16,591
Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables
Owen, D. B., Abramowitz, M., & Stegun, I. A. (1965) · Technometrics · doi:10.2307/1266136 · Cited by 16,138
An Introduction to Multivariate Statistical Analysis
Muirhead, R. J., & Anderson, T. W. (1986) · Journal of Business & Economic Statistics · doi:10.2307/1391399 · Cited by 9,082
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
NIST Handbook of Mathematical Functions
Olver, F. W. J., Lozier, D. W., Boisvert, R. F., & Clark, C. W. (2010) · CERN Document Server (European Organization for Nuclear Research) · Cited by 5,206
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
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Convex Bodies: The Brunn–Minkowski Theory
Schneider, R. (1993) · Cambridge University Press eBooks · doi:10.1017/cbo9780511526282 · Cited by 3,345
An Introduction to Multivariate Statistical Analysis.
Skinner, C. J., & Anderson, T. W. (1985) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2981950 · Cited by 3,245
Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables.
H., C., Abramowitz, M., & Stegun, I. A. (1964) · Journal of the American Statistical Association · doi:10.2307/2282672 · Cited by 3,073
A Mathematical Introduction to Compressive Sensing
Foucart, S., & Rauhut, H. (2013) · Applied and Numerical Harmonic Analysis · doi:10.1007/978-0-8176-4948-7 · Cited by 2,548
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
Convex Analysis and Minimization Algorithms I
Hiriart-Urruty, J.-B., & Lemaréchal, C. (1993) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-02796-7 · Cited by 2,378
Ziegler, G. M. (1995) · Graduate Texts in Mathematics · doi:10.1007/978-1-4613-8431-1 · Cited by 2,329
Integral Geometry and Geometric Probability
Santaló, L. A., & Kac, M. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511617331 · Cited by 1,794
Concentration Inequalities: A Nonasymptotic Theory of Independence
Boucheron, S., Lugosi, G., & Massart, P. (2013) · doi:10.1093/acprof:oso/9780199535255.001.0001 · Cited by 1,768
The Concentration of Measure Phenomenon
Ledoux, M. (2005) · Mathematical Surveys and Monographs · doi:10.1090/surv/089 · Cited by 1,700
Spectral Analysis of Large Dimensional Random Matrices
Bai, Z., & Silverstein, J. W. (2010) · Springer Series in Statistics · doi:10.1007/978-1-4419-0661-8 · Cited by 1,544
Alizadeh, F., & Goldfarb, D. (2003) · Mathematical Programming · doi:10.1007/s10107-002-0339-5 · Cited by 1,500
Generators and Relations for Discrete Groups
Coxeter, H. S. M., & Moser, W. O. J. (1972) · Springer eBooks · doi:10.1007/978-3-662-21946-1 · Cited by 1,480
Stochastic and Integral Geometry
Schneider, R., & Weil, W. (2008) · Probability and Its Applications · doi:10.1007/978-3-540-78859-1 · Cited by 992
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
The Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2010) · Cited by 921
Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)
Elad, M., Starck, J.-L., Querre, P., & Donoho, D. L. (2005) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2005.03.005 · Cited by 904
On sparse reconstruction from Fourier and Gaussian measurements
Rudelson, M., & Vershynin, R. (2008) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20227 · Cited by 847
Robust Modeling With Erratic Data
Claerbout, J. F., & Muir, F. (1973) · Geophysics · doi:10.1190/1.1440378 · Cited by 833
Gesammelte Mathematische Abhandlungen: Erster Band
Schwarz, H. A. (1890) · Springer eBooks · doi:10.1007/978-3-642-50665-9 · Cited by 827
Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications
Ben-Tal, A., & Nemirovski, A. (2001) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718829 · Cited by 747
Linear Inversion of Band-Limited Reflection Seismograms
Santosa, F., & Symes, W. W. (1986) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0907087 · Cited by 713
Weyl, H. (1939) · American Journal of Mathematics · doi:10.2307/2371513 · Cited by 476
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
High-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
Characterization of the subdifferential of some matrix norms
Watson, G. A. (1992) · Linear Algebra and its Applications · doi:10.1016/0024-3795(92)90407-2 · Cited by 364
Generators and Relations for Discrete Groups
Coxeter, H. S. M., & Moser, W. O. J. (1957) · Springer eBooks · doi:10.1007/978-3-662-25739-5 · Cited by 342
On Milman's inequality and random subspaces which escape through a mesh in ℝ n
Gordon, Y. (1988) · Lecture Notes in Mathematics · doi:10.1007/bfb0081737 · Cited by 282
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
Astronomical image representation by the curvelet transform
Starck, J. L., Donoho, D. L., & Candès, E. J. (2003) · Astronomy & Astrophysics · doi:10.1051/0004-6361:20021571 · Cited by 264
Universality in polytope phase transitions and message passing algorithms
Bayati, M., Lelarge, M., & Andrea Montanari, A. (2015) · The Annals of Applied Probability · doi:10.1214/14-aap1010 · Cited by 209
Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
Mu, C., Huang, B., Wright, J. N., & Goldfarb, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.5870 · Cited by 203
On the rank minimization problem over a positive semidefinite linear matrix inequality
Mesbahi, M., & Papavassilopoulos, G. P. (1997) · IEEE Transactions on Automatic Control · doi:10.1109/9.554402 · Cited by 199
How to generate random matrices from the classical compact groups
Mezzadri, F. (2007) · Cited by 198
How to generate random matrices from the classical compact groups
Mezzadri, F. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math-ph/0609050 · Cited by 185
A Mathematical Introduction to Compressive Sensing
廣瀬, 慧. (2015) · 日本統計学会誌 · doi:10.11329/jjssj.44.501 · Cited by 184
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
Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
Donoho, D. L., Johnstone, I., & Montanari, A. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2239356 · Cited by 177
Random projections of regular simplices
Affentranger, F., & Schneider, R. (1992) · Discrete & Computational Geometry · doi:10.1007/bf02187839 · Cited by 114
Steinberg, R. (1959) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1959-0106428-2 · Cited by 104
Sharp MSE Bounds for Proximal Denoising
Oymak, S., & Hassibi, B. (2015) · Foundations of Computational Mathematics · doi:10.1007/s10208-015-9278-4 · Cited by 92
New Null Space Results and Recovery Thresholds for Matrix Rank MinimizationPreprint
Oymak, S., & Hassibi, B. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.6326 · Cited by 91
Sharp Recovery Bounds for Convex Demixing, with Applications
McCoy, M. B., & Tropp, J. A. (2014) · Foundations of Computational Mathematics · doi:10.1007/s10208-014-9191-2 · Cited by 87
Self-citationAnti-sparse coding for approximate nearest neighbor search
Jeǵou, H., Furon, T., & Fuchs, J. (2012) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2012.6288307 · Cited by 82
Donoho, D. L., Gavish, M., & Montanari, A. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1306110110 · Cited by 57
The Achievable Performance of Convex DemixingPreprint
McCoy, M. B., & Tropp, J. A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.7478 · Cited by 46
Self-citationThe CVX Users' Guide Release 2.0 (beta)
Grant, M. C., & Boyd, S. (2013) · Cited by 31
On Parallel Hypersurfaces in the Elliptic and Hyperbolic n-Dimensional Space
Santaló, L. (1950) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1950-0036532-6 · Cited by 25
Cited by
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
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
Randomized numerical linear algebra: Foundations and algorithms
Martinsson, P.-G., & Tropp, J. A. (2020) · Acta Numerica · doi:10.1017/s0962492920000021 · Cited by 300
Self-citationSimultaneously Structured Models With Application to Sparse and Low-Rank Matrices
Oymak, S., Jalali, A., Fazel, M., Eldar, Y. C., & Hassibi, B. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2401574 · Cited by 252
Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
Sun, J., Qu, Q., & Wright, J. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632162 · Cited by 213
Metadata
- Authors
- Amelunxen, D., Lotz, M., McCoy, M. B., & Tropp, J. A.
- Venue
- Information and Inference
- Publisher
- Oxford University Press (OUP)
- Published
- 2014-06-30
- Volume
- 3
- Issue
- 3
- Pages
- 224-294
- ISSN
- 2049-8764 (ISSN-L)
- 2049-8772
- OpenAlex
- W2025223969
- Cited by
- 413
- References
- 59
- FWCI
- 42.72
- Type
- journal article
- Language
- en
- Open access
- bronze
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.