Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
From MaRDI portal
Publication:3559946
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- universality across matrix ensembles; finite-sample universality can be rejected.
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
Cites work
Cited in
(71)- 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
- High-dimensional regression with unknown variance
- Empirical average-case relation between undersampling and sparsity in X-ray CT
- Random cones in high dimensions. I: Donoho-Tanner and Cover-Efron cones.
- Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks
- Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
- Universality in polytope phase transitions and message passing algorithms
- Threshold phenomena for random cones
- Sharp recovery bounds for convex demixing, with applications
- Sparse Legendre expansions via _1-minimization
- LASSO risk and phase transition under dependence
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- A power analysis for Model-X knockoffs with \(\ell_p\)-regularized statistics
- Geometry and applied statistics
- Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator
- Computing and analyzing recoverable supports for sparse reconstruction
- General stochastic separation theorems with optimal bounds
- 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
- Theory and applications of compressed sensing
- Replica approach to mean-variance portfolio optimization
- Derandomized compressed sensing with nonuniform guarantees for _1 recovery
- Characterizing the SLOPE trade-off: a variational perspective and the Donoho-Tanner limit
- Recovering structured signals in noise: least-squares meets compressed sensing
- Minimax risks for sparse regressions: ultra-high dimensional phenomenons
- Two are better than one: fundamental parameters of frame coherence
- A discussion on practical considerations with sparse regression methodologies
- Sparse recovery from extreme eigenvalues deviation inequalities
- A numerical exploration of compressed sampling recovery
- Universality of approximate message passing algorithms and tensor networks
- The restricted isometry property of block diagonal matrices for group-sparse signal recovery
- Analytic approach to variance optimization under an \(\mathcal{l}_1\) constraint
- The restricted isometry property for random block diagonal matrices
- Sharp MSE bounds for proximal denoising
- Correction of AI systems by linear discriminants: probabilistic foundations
- The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
- Analysis _1-recovery with frames and Gaussian measurements
- Expander \(\ell_0\)-decoding
- An introduction to compressed sensing
- Book Review: A mathematical introduction to compressive sensing
- Effect of global shrinkage parameter of horseshoe prior in compressed sensing
- Performance comparisons of greedy algorithms in compressed sensing.
- Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
- Analytic solution to variance optimization with no short positions
- Approximation of classifiers by deep perceptron networks
- Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
- On the universality of noiseless linear estimation with respect to the measurement matrix
- Melting phenomena of self-organized magnetic structures investigated by variational autoencoder
- Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized X-ray CT
- Energy preserved sampling for compressed sensing MRI
- 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
- Concentration of the Frobenius norm of generalized matrix inverses
- 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
- A Rice method proof of the null-space property over the Grassmannian
- Consistent parameter estimation for Lasso and approximate message passing
- Phase transitions in error correcting and compressed sensing by \(\ell _{1}\) linear programming
- On a game of chance in Marc Elsberg's thriller ``GREED
- Counting the faces of randomly-projected hypercubes and orthants, with applications
- Sparse decomposition by iterating Lipschitzian-type mappings
- Statistical mechanics of complex economies
- Flavors of compressive sensing
- Universality of approximate message passing with semirandom matrices
- The Lasso with general Gaussian designs with applications to hypothesis testing
- A simple homotopy proximal mapping algorithm for compressive sensing
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)
