Universality in polytope phase transitions and message passing algorithms

Abstract

We consider a class of nonlinear mappings ${\mathsf{F}}_{A,N}$ in ${\mathbb{R}}^N$ indexed by symmetric random matrices $A\in {\mathbb{R}}^{N\times N}$ with independent entries. Within spin glass theory, special cases of these mappings correspond to iterating the TAP equations and were studied by Bolthausen [Comm. Math. Phys. 325 (2014) 333-366]. Within information theory, they are known as "approximate message passing" algorithms. We study the high-dimensional (large $N$) behavior of the iterates of $\mathsf{F}$ for polynomial functions $\mathsf{F}$, and prove that it is universal; that is, it depends only on the first two moments of the entries of $A$, under a sub-Gaussian tail condition. As an application, we prove the universality of a certain phase transition arising in polytope geometry and compressed sensing. This solves, for a broad class of random projections, a conjecture by David Donoho and Jared Tanner.

Published in at http://dx.doi.org/10.1214/14-AAP1010 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (7)

• Message Passing Algorithms for Compressed Sensing
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Statistical physics-based reconstruction in compressed sensing
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• Random matrices: The Universality phenomenon for Wigner ensembles

Cited by in corpus (65)

• AMP-Inspired Deep Networks for Sparse Linear Inverse Problems
• Statistical physics of inference: Thresholds and algorithms
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• How little data is enough? Phase-diagram analysis of sparsity-regularized X-ray CT
• The Mutual Information in Random Linear Estimation
• Hybrid Approximate Message Passing
• A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Convexity in source separation: Models, geometry, and algorithms
• Finite Sample Analysis of Approximate Message Passing Algorithms
• The Lasso with general Gaussian designs with applications to hypothesis testing
• Disordered Systems Insights on Computational Hardness
• Bilinear Recovery using Adaptive Vector-AMP
• Convolutional Approximate Message-Passing
• The committee machine: Computational to statistical gaps in learning a two-layers neural network
• Living on the edge: Phase transitions in convex programs with random data
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing
• Memory-free dynamics for the TAP equations of Ising models with arbitrary rotation invariant ensembles of random coupling matrices
• Limits on Sparse Data Acquisition: RIC Analysis of Finite Gaussian Matrices
• Performance Limits for Noisy Multi-Measurement Vector Problems
• Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
• Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
• The Gaussian min-max theorem in the Presence of Convexity
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• False Discoveries Occur Early on the Lasso Path
• Optimizing Mean Field Spin Glasses with External Field
• On the Error in Phase Transition Computations for Compressed Sensing
• Which bridge estimator is optimal for variable selection?
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Rigorous dynamical mean field theory for stochastic gradient descent methods
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Robustness of Sparse Recovery via $F$-minimization: A Topological Viewpoint
• Sharp recovery bounds for convex demixing, with applications
• Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• Sample-Optimal Fourier Sampling in Any Constant Dimension -- Part I
• An equivalence between high dimensional Bayes optimal inference and M-estimation
• Statistical Physics and Information Theory Perspectives on Linear Inverse Problems
• Analysis of Bayesian Inference Algorithms by the Dynamical Functional Approach
• Properties of spatial coupling in compressed sensing
• On Sparse Vector Recovery Performance in Structurally Orthogonal Matrices via LASSO
• Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent
• A Unified Framework of State Evolution for Message-Passing Algorithms
• Asymptotic MMSE Analysis Under Sparse Representation Modeling
• Understanding the Under-Coverage Bias in Uncertainty Estimation
• Empirical Bayes PCA in high dimensions
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions
• Bernoulli-Gaussian Approximate Message-Passing Algorithm for Compressed Sensing with 1D-Finite-Difference Sparsity
• Grant-Free Access via Bilinear Inference for Cell-Free MIMO with Low-Coherent Pilots
• Asymptotic Performance Prediction for ADMM-Based Compressed Sensing
• Bayes-Optimal Convolutional AMP
• Phase Transition of Convex Programs for Linear Inverse Problems with Multiple Prior Constraints
• Universality of Approximate Message Passing Algorithms
• Approximate Message Passing for Underdetermined Audio Source Separation
• Asymptotic Statistical Analysis of Sparse Group LASSO via Approximate Message Passing Algorithm
• The Complete Lasso Tradeoff Diagram
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective