Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing

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.

47 pages, 24 figures, 10 tables

References in corpus (1)

• Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing

Cited by in corpus (106)

• Message Passing Algorithms for Compressed Sensing
• Structured Compressed Sensing: From Theory to Applications
• Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing
• Imaging With Nature: Compressive Imaging Using a Multiply Scattering Medium
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• Universality in polytope phase transitions and message passing algorithms
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach
• Convex Optimization Approaches for Blind Sensor Calibration using Sparsity
• Two are better than one: Fundamental parameters of frame coherence
• How little data is enough? Phase-diagram analysis of sparsity-regularized X-ray CT
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Correction of AI systems by linear discriminants: Probabilistic foundations
• The unreasonable effectiveness of small neural ensembles in high-dimensional brain
• Statistical estimation and testing via the sorted L1 norm
• Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized x-ray CT
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Cross validation in LASSO and its acceleration
• Phase Transitions in Frequency Agile Radar Using Compressed Sensing
• Reconstruction of Signals Drawn from a Gaussian Mixture from Noisy Compressive Measurements
• High--Dimensional Brain in a High-Dimensional World: Blessing of Dimensionality
• Block-length dependent thresholds in block-sparse compressed sensing
• Orthonormal Expansion l1-Minimization Algorithms for Compressed Sensing
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Sparse Classification: a scalable discrete optimization perspective
• Compressive Sensing with Cross-Validation and Stop-Sampling for Sparse Polynomial Chaos Expansions
• On Phase Transition of Compressed Sensing in the Complex Domain
• A Constrained Random Demodulator for Sub-Nyquist Sampling
• Living on the edge: Phase transitions in convex programs with random data
• High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing
• High Speed Compressed Sensing Reconstruction in Dynamic Parallel MRI Using Augmented Lagrangian and Parallel Processing
• Statistical mechanics of complex economies
• Belief Propagation Reconstruction for Discrete Tomography
• Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets
• Knowledge Elicitation via Sequential Probabilistic Inference for High-Dimensional Prediction
• General stochastic separation theorems with optimal bounds
• Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
• Replica approach to mean-variance portfolio optimization
• The Gaussian min-max theorem in the Presence of Convexity
• Restricted isometry property of random subdictionaries
• Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
• The generalized Lasso with non-linear observations
• Analytic solution to variance optimization with no short-selling
• Sharp MSE Bounds for Proximal Denoising
• Gaussian Universality of Perceptrons with Random Labels
• False Discoveries Occur Early on the Lasso Path
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• A Unified Framework for Sparse Relaxed Regularized Regression: SR3
• Near-optimal matrix recovery from random linear measurements
• Augmented Artificial Intelligence: a Conceptual Framework
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• Sharp recovery bounds for convex demixing, with applications
• Robustness of Sparse Recovery via $F$-minimization: A Topological Viewpoint
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• Efficient Least Residual Greedy Algorithms for Sparse Recovery
• 3D Shape Estimation from 2D Landmarks: A Convex Relaxation Approach
• WHInter: A Working set algorithm for High-dimensional sparse second order Interaction models
• Universality in Learning from Linear Measurements
• Random cones in high dimensions I: Donoho-Tanner and Cover-Efron cones
• Analysis ${\ell }_1$-recovery with frames and Gaussian measurements
• Fast Marginalized Block Sparse Bayesian Learning Algorithm
• An Energy Based Scheme for Reconstruction of Piecewise Constant Signals observed in the Movement of Molecular Machines
• Symphony of high-dimensional brain
• Application of compressed sensing to genome wide association studies and genomic selection
• Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
• Sparse Legendre expansions via ${\ell }_1$ minimization
• Convolutional Sparse Support Estimator Network (CSEN) From energy efficient support estimation to learning-aided Compressive Sensing
• Sparse Signal Processing with Frame Theory
• Support vector machines and linear regression coincide with very high-dimensional features
• Phase transition in compressed sensing with horseshoe prior
• On Sparse Vector Recovery Performance in Structurally Orthogonal Matrices via LASSO
• A Discussion on Practical Considerations with Sparse Regression Methodologies
• Empirical average-case relation between undersampling and sparsity in x-ray CT
• High Dimensional Linear Regression using Lattice Basis Reduction
• Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation
• Subwavelength imaging of sparse broadband sources surrounded by an open disordered medium from a single antenna
• Critical Behavior and Universality Classes for an Algorithmic Phase Transition in Sparse Reconstruction
• How can one sample images with sampling rates close to the theoretical minimum?
• Linear and Fisher Separability of Random Points in the d-dimensional Spherical Layer
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search
• Sparse Recovery from Extreme Eigenvalues Deviation Inequalities
• Optimization for Compressed Sensing: the Simplex Method and Kronecker Sparsification
• Sparsity/Undersampling Tradeoffs in Anisotropic Undersampling, with Applications in MR Imaging/Spectroscopy
• Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery
• Linear under-determined systems with sparse solutions: Redirecting a challenge?
• Characterizing the SLOPE Trade-off: A Variational Perspective and the Donoho-Tanner Limit
• Expander ${\ell }_0$-Decoding
• High-dimensional regression with unknown variance
• Sparse Models for Machine Learning
• Analytic approach to variance optimization under an ${\ell }_1$ constraint
• Effect of global shrinkage parameter of horseshoe prior in compressed sensing
• Deterministic Constructions of Binary Measurement Matrices from Finite Geometry
• DebiNet: Debiasing Linear Models with Nonlinear Overparameterized Neural Networks
• The General sampling theorem, Compressed sensing and a method of image sampling and reconstruction with sampling rates close to the theoretical limit
• Aspects of a phase transition in high-dimensional random geometry
• LASSO risk and phase transition under dependence
• The Complete Lasso Tradeoff Diagram
• A study of the universal threshold in the L1 recovery by statistical mechanics