The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
Open accessAbstract
We review connections between phase transitions in high-dimensional combinatorial geometry and phase transitions occurring in modern high-dimensional data analysis and signal processing. In data analysis, such transitions arise as abrupt breakdown of linear model selection, robust data fitting or compressed sensing reconstructions, when the complexity of the model or the number of outliers increases beyond a threshold. In combinatorial geometry, these transitions appear as abrupt changes in the properties of face counts of convex polytopes when the dimensions are varied. The thresholds in these very different problems appear in the same critical locations after appropriate calibration of variables. These thresholds are important in each subject area: for linear modelling, they place hard limits on the degree to which the now ubiquitous high-throughput data analysis can be successful; for robustness, they place hard limits on the degree to which standard robust fitting methods can tolerate outliers before breaking down; for compressed sensing, they define the sharp boundary of the undersampling/sparsity trade-off curve in undersampling theorems. Existing derivations of phase transitions in combinatorial geometry assume that the underlying matrices have independent and identically distributed Gaussian elements. In applications, however, it often seems that Gaussianity is not required. We conducted an extensive computational experiment and formal inferential analysis to test the hypothesis that these phase transitions are universal across a range of underlying matrix ensembles. We ran millions of linear programs using random matrices spanning several matrix ensembles and problem sizes; visually, the empirical phase transitions do not depend on the ensemble, and they agree extremely well with the asymptotic theory assuming Gaussianity. Careful statistical analysis reveals discrepancies that can be explained as transient terms, decaying with problem size. The experimental results are thus consistent with an asymptotic large- n universality across matrix ensembles; finite-sample universality can be rejected.
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
Sparse nonnegative solution of underdetermined linear equations by linear programming
Donoho, D. L., & Tanner, J. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0502269102 · Cited by 577
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-citationOptimally 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-citationCounting 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-citationAdamczak, R., Litvak, A. E., Pajor, A., & Nicole Tomczak-jaegermann, B. (2010) · Constructive Approximation · doi:10.1007/s00365-010-9117-4 · Cited by 123
Cited by
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-citationStructured Compressed Sensing: From Theory to Applications
Duarte, M. F., & Eldar, Y. C. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2161982 · Cited by 1,128
Extension of SBL Algorithms for the Recovery of Block Sparse Signals With Intra-Block Correlation
Zhang, Z., & Rao, B. D. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2241055 · Cited by 558
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
Statistical challenges of high-dimensional data
Johnstone, I. M., & Titterington, D. M. (2009) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2009.0159 · Cited by 417
Metadata
- Authors
- Donoho, D., & Tanner, J.
- Venue
- Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Publisher
- The Royal Society
- Published
- 2009-11-13
- Volume
- 367
- Issue
- 1906
- Pages
- 4273-4293
- ISSN
- 1364-503X (ISSN-L)
- 1471-2962
- OpenAlex
- W2144006746
- Cited by
- 436
- References
- 5
- FWCI
- 21.59
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. https://app.cochat.ai/papers/10.1098/rsta.2009.0152
- The paper
- Donoho, D., & Tanner, J. (2009). Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. https://doi.org/10.1098/rsta.2009.0152
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.