Universality in polytope phase transitions and message passing algorithms

DOI10.1214/14-AAP1010zbMath1322.60207arXiv1207.7321MaRDI QIDQ2341631

Marc Lelarge, Mohsen Bayati, Andrea Montanari

Publication date: 27 April 2015

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

random matricesuniversalitymessage passing algorithmscompressed sensingpolytope phase transitions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Random matrices (probabilistic aspects) (60B20) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Related Items (44)

Fundamental barriers to high-dimensional regression with convex penalties ⋮ Approximate message passing algorithms for rotationally invariant matrices ⋮ Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information ⋮ Disordered systems insights on computational hardness ⋮ Book Review: A mathematical introduction to compressive sensing ⋮ Analysis of Bayesian inference algorithms by the dynamical functional approach ⋮ On the universality of noiseless linear estimation with respect to the measurement matrix ⋮ Sharp MSE bounds for proximal denoising ⋮ High dimensional robust M-estimation: asymptotic variance via approximate message passing ⋮ Estimation of low-rank matrices via approximate message passing ⋮ An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model ⋮ Algorithmic pure states for the negative spherical perceptron ⋮ Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising ⋮ Sharp recovery bounds for convex demixing, with applications ⋮ Fundamental limits of weak recovery with applications to phase retrieval ⋮ A theory of capacity and sparse neural encoding ⋮ Facets of spherical random polytopes ⋮ Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time ⋮ Approximate message passing for sparse matrices with application to the equilibria of large ecological Lotka-Volterra systems ⋮ Optimization algorithms for multi-species spherical spin glasses ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Universality of approximate message passing with semirandom matrices ⋮ A Message-Passing Approach to Phase Retrieval of Sparse Signals ⋮ Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization ⋮ Universality of regularized regression estimators in high dimensions ⋮ The Lasso with general Gaussian designs with applications to hypothesis testing ⋮ Optimizing mean field spin glasses with external field ⋮ Asymptotic mutual information for the balanced binary stochastic block model ⋮ Which bridge estimator is the best for variable selection? ⋮ Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator ⋮ The overlap gap property and approximate message passing algorithms for \(p\)-spin models ⋮ Optimization of the Sherrington--Kirkpatrick Hamiltonian ⋮ Debiasing the Lasso: optimal sample size for Gaussian designs ⋮ Consistent parameter estimation for Lasso and approximate message passing ⋮ Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices ⋮ The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square ⋮ Diffusions interacting through a random matrix: universality via stochastic Taylor expansion ⋮ Universality of approximate message passing algorithms ⋮ Optimization of mean-field spin glasses ⋮ The committee machine: computational to statistical gaps in learning a two-layers neural network ⋮ A Unifying Tutorial on Approximate Message Passing ⋮ LASSO risk and phase transition under dependence ⋮ Replica analysis of overfitting in generalized linear regression models ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Spectral analysis of large dimensional random matrices
• Random projections of regular simplices
• No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• Smoothed Analysis of Moore–Penrose Inversion
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• An Introduction to Random Matrices
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• The LASSO Risk for Gaussian Matrices
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
• Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Neighborliness of randomly projected simplices in high dimensions

This page was built for publication: Universality in polytope phase transitions and message passing algorithms