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

DOI10.1098/RSTA.2009.0152zbMATH Open1185.94029arXiv0906.2530OpenAlexW2144006746WikidataQ33508769 ScholiaQ33508769MaRDI QIDQ3559946FDOQ3559946

Authors: David Donoho, Jared Tanner 

Publication date: 8 May 2010

Published in: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Abstract: 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 tradeoff in undersampling theorems. Existing derivations of phase transitions in combinatorial geometry assume the underlying matrices have independent and identically distributed (iid) 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 {it universal} across a range of underlying matrix ensembles. The experimental results are consistent with an asymptotic large-$n$ universality across matrix ensembles; finite-sample universality can be rejected.

Full work available at URL: https://arxiv.org/abs/0906.2530

Recommendations

• Universality in polytope phase transitions and message passing algorithms
• Living on the edge: phase transitions in convex programs with random data
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• Phase transition in limiting distributions of coherence of high-dimensional random matrices
• Universality laws for randomized dimension reduction, with applications

zbMATH Keywords

compressed sensingcombinatorial geometryrobust linear modelshigh dimension low sample size datasetshigh-throughput measurements

Mathematics Subject Classification ID

Inference from spatial processes (62M30) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Measures of information, entropy (94A17)

Cites Work

• Feature selection by higher criticism thresholding achieves the optimal phase diagram
• Neighborliness of randomly projected simplices in high dimensions

Cited In (71)

• A power analysis for Model-X knockoffs with \(\ell_p\)-regularized statistics
• Geometry and applied statistics
• General stochastic separation theorems with optimal bounds
• Characterizing the SLOPE trade-off: a variational perspective and the Donoho-Tanner limit
• Universality of approximate message passing algorithms and tensor networks
• Analytic approach to variance optimization under an \(\mathcal{l}_1\) constraint
• An introduction to compressed sensing
• Effect of global shrinkage parameter of horseshoe prior in compressed sensing
• On the universality of noiseless linear estimation with respect to the measurement matrix
• Melting phenomena of self-organized magnetic structures investigated by variational autoencoder
• Universality of approximate message passing with semirandom matrices
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• Empirical average-case relation between undersampling and sparsity in X-ray CT
• Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks
• Universality in polytope phase transitions and message passing algorithms
• Threshold phenomena for random cones
• Sharp recovery bounds for convex demixing, with applications
• LASSO risk and phase transition under dependence
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Sparse high-dimensional regression: exact scalable algorithms and phase transitions
• Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator
• Computing and analyzing recoverable supports for sparse reconstruction
• Cross validation in Lasso and its acceleration
• Sparse classification: a scalable discrete optimization perspective
• Image reconstruction from undersampled Fourier data using the polynomial annihilation transform
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• Replica approach to mean-variance portfolio optimization
• Theory and applications of compressed sensing
• Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
• Recovering structured signals in noise: least-squares meets compressed sensing
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• Sparse recovery from extreme eigenvalues deviation inequalities
• Two are better than one: fundamental parameters of frame coherence
• A discussion on practical considerations with sparse regression methodologies
• A numerical exploration of compressed sampling recovery
• The restricted isometry property of block diagonal matrices for group-sparse signal recovery
• The restricted isometry property for random block diagonal matrices
• The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
• Correction of AI systems by linear discriminants: probabilistic foundations
• Sharp MSE bounds for proximal denoising
• Expander \(\ell_0\)-decoding
• Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
• Book Review: A mathematical introduction to compressive sensing
• Title not available (Why is that?)
• Performance comparisons of greedy algorithms in compressed sensing.
• Analytic solution to variance optimization with no short positions
• Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
• Approximation of classifiers by deep perceptron networks
• Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
• Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized X-ray CT
• Energy preserved sampling for compressed sensing MRI
• Concentration of the Frobenius norm of generalized matrix inverses
• The essential ability of sparse reconstruction of different compressive sensing strategies
• Sparse microwave imaging: principles and applications
• Sparse SAR imaging based on \(L_{1/2}\) regularization
• Knowledge elicitation via sequential probabilistic inference for high-dimensional prediction
• PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting
• Partial gradient optimal thresholding algorithms for a class of sparse optimization problems
• Consistent parameter estimation for Lasso and approximate message passing
• A Rice method proof of the null-space property over the Grassmannian
• Phase transitions in error correcting and compressed sensing by \(\ell _{1}\) linear programming
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• On a game of chance in Marc Elsberg's thriller ``GREED
• Flavors of compressive sensing
• Statistical mechanics of complex economies
• Sparse decomposition by iterating Lipschitzian-type mappings
• The Lasso with general Gaussian designs with applications to hypothesis testing
• A simple homotopy proximal mapping algorithm for compressive sensing
• High-dimensional regression with unknown variance
• Compressive sensing with cross-validation and stop-sampling for sparse polynomial chaos expansions
• Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction

This page was built for publication: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3559946)