Universality of approximate message passing algorithms

DOI10.1214/21-EJP604zbMath1483.60007arXiv2003.10431OpenAlexW3158809943MaRDI QIDQ2042851

Wei-Kuo Chen, Wai-Kit Lam

Publication date: 21 July 2021

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

universalitymessage passingspike recoveryspiked random matrix

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52)

Related Items

Approximate message passing algorithms for rotationally invariant matrices, Ultrametricity in spin glasses, 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, A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists, Universality of approximate message passing with semirandom matrices, Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization, Universality of regularized regression estimators in high dimensions, Optimizing mean field spin glasses with external field, A Unifying Tutorial on Approximate Message Passing

Cites Work

• Unnamed Item
• The singular values and vectors of low rank perturbations of large rectangular random matrices
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The largest eigenvalue of small rank perturbations of Hermitian random matrices
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• On the distribution of the largest eigenvalue in principal components analysis
• Universality in polytope phase transitions and message passing algorithms
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Eigenvalues of large sample covariance matrices of spiked population models
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Estimation of low-rank matrices via approximate message passing
• The Isotropic Semicircle Law and Deformation of Wigner Matrices
• Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Bilinear Generalized Approximate Message Passing—Part II: Applications
• Asymptotic mutual information for the balanced binary stochastic block model
• High-Dimensional Probability
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing