Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing

By David L. Donoho, Jared Tanner. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2009

472 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/1c0020729aff489a483532e6208507963e38a2a1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Expectation-Maximization Gaussian-Mixture Approximate Message Passing (2012, background): “…Engineering, The Ohio State University, Columbus, OH 43210 USA (e-mail: vila.2@osu.edu; schniter@ece.osu.edu). constructed from i.i.d zero-mean sub-Gaussian entries, the performance of LASSO can be sharply characterized in the large system limit (i.e., asK,M,N → ∞ with fixed undersampling…”
Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation (2014, methodology): “Since there will be several types of outliers in real-world problems, we generate outliers in a different way from [27].”
High-dimensional regression with unknown variance (2011, background): “This kind of phase transition has been observed in a wide range of random geometry problems [29], suggesting some universality in this limitation.”
Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization (2012, background): “continue to be faces after a random projection into a lower-dimensional space. While we have only considered a speciﬁc instance of the class Ens+, it is unlikely − not least because of the ﬁndings in [18] − that the results should depend on the speciﬁc probability distribution of the entries, provid”
Precise Undersampling Theorems (2010, background): “In fact, Theorem 1 is known to be true for matrices other than Gaussian as well; the function � ð� ;IÞ is equally true for any matrix in general position [10], empirical evidence suggests that � ð� ;CÞ and � ð� ;TÞ are equally true for an as of yet unknown broader class of matrices [ 17 ].”
The Noise-Sensitivity Phase Transition in Compressed Sensing (2010, background): “Previously, extensive empirical evidence was presented by Donoho and Tanner [20], that pure -minimization has its - equivalence phase transition at the boundary not only for Gaussian matrices but for a wide collection of ensembles, including partial Fourier, partial Hadamard, expander graphs, i.”
Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices (2012, background): “`1 minimization [7, 24, 52], and to the information theoretic limit for exact reconstruction α = ρ.”
Optimal errors and phase transitions in high-dimensional generalized linear models (2017, methodology): “the realization that, using the `1 norm minimization technique, one can e ciently recover the signal for larger α values than the so-called Donoho-Tanner transition [11, 81].”
Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach (2015, background): “This observation is analogous to the phase transition in compressive sensing, where the recovery probability also depends on the number of observations and the underlying signal sparsity [51].”
Structured Compressed Sensing: From Theory to Applications (2011, unknown): “…RIP-fulﬁlling matrices provided above might seem limited, emerging numerical results have shown that a variety of classes of matrices are suitable for CS recovery at regimes similar to those of the matrices advocated in this section, including subsampled Fourier and Hadamard transforms [47], [48].”
Message-passing algorithms for compressed sensing (2009, background): “The results for the three cases are presented in Figures 7, 8, 9.”
Living on the edge: phase transitions in convex programs with random data (2013, background): “Numerical experiments [36] suggest that this bound is sharp, but the theoretical analysis in [29] falls short of establishing that a phase transition actually exists and identifying its location rigorously.”
Minimax risks for sparse regressions: Ultra-high-dimensional phenomenons (2010, unknown): “In noiseless problems (σ = 0), compressed sensing methods [23] fail when k[1+log(p/k)] is large compared to n (see [22] for numerical illustrations).”
Extension of SBL Algorithms for the Recovery of Block Sparse Signals With Intra-Block Correlation (2012, methodology): “We first examined empirical phase transitions [20]5 in exact recovery of block sparse signals in noiseless environments for our three BSBL algorithms, Block-OMP, Model-CoSaMP, Mixed Program, and Group Basis Pursuit.”