The DOI matches its Crossref record; 57 of the 57 references it cites were found in a registry or an index.
Living on the edge: phase transitions in convex programs with random data
Open accessAbstract
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.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
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,703
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
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
- 57
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Living on the edge: phase transitions in convex programs with random data. https://app.cochat.ai/papers/10.1093/imaiai/iau005
- The paper
- Amelunxen, D., Lotz, M., McCoy, M. B., & Tropp, J. A. (2014). Living on the edge: phase transitions in convex programs with random data. Information and Inference. https://doi.org/10.1093/imaiai/iau005
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.