Universality of approximate message passing with semirandom matrices

DOI10.1214/23-AOP1628MaRDI QIDQ6142946zbMATH OpenOpenAlexFDO

Authors

Publication date 23 January 2024

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

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

zbMATH Keywords

message passingrandom matricesspin glassesuniversality

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Analysis of algorithms (68W40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Abstract: Approximate Message Passing (AMP) is a class of iterative algorithms that have found applications in many problems in high-dimensional statistics and machine learning. In its general form, AMP can be formulated as an iterative procedure driven by a matrix $mathbfM$. Theoretical analyses of AMP typically assume strong distributional properties on $mathbfM$ such as $mathbfM$ has i.i.d. sub-Gaussian entries or is drawn from a rotational invariant ensemble. However, numerical experiments suggest that the behavior of AMP is universal, as long as the eigenvectors of $mathbfM$ are generic. In this paper, we take the first step in rigorously understanding this universality phenomenon. In particular, we investigate a class of memory-free AMP algorithms (proposed by c{C}akmak and Opper for mean-field Ising spin glasses), and show that their asymptotic dynamics is universal on a broad class of semi-random matrices. In addition to having the standard rotational invariant ensemble as a special case, the class of semi-random matrices that we define in this work also includes matrices constructed with very limited randomness. One such example is a randomly signed version of the Sine model, introduced by Marinari, Parisi, Potters, and Ritort for spin glasses with fully deterministic couplings.

Recommendations

• Universality of approximate message passing algorithms
• Universality of approximate message passing algorithms and tensor networks
• Approximate message passing algorithms for rotationally invariant matrices
• A Unifying Tutorial on Approximate Message Passing
• Approximate message passing for orthogonally invariant ensembles: multivariate non-linearities and spectral initialization

Cites work

• A CDMA multiuser detection algorithm on the basis of belief propagation
• A Dynamical Approach to Random Matrix Theory
• A modern maximum-likelihood theory for high-dimensional logistic regression
• A Problem in Geometric Probability.
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Analysis of Boolean Functions
• Applications of the Lindeberg Principle in Communications and Statistical Learning
• Approximate message passing algorithms for rotationally invariant matrices
• Approximate message passing with spectral initialization for generalized linear models*
• Asymptotically liberating sequences of random unitary matrices
• Capacity of Channels With Frequency-Selective and Time-Selective Fading
• Capacity-Achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Concentration inequalities for sums and martingales
• Concentration inequalities. A nonasymptotic theory of independence
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Estimation of low-rank matrices via approximate message passing
• Expectation consistent approximate inference
• Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles
• scientific article; zbMATH DE number 1138484 (Why is no real title available?)
• Information, Physics, and Computation
• Isotropic local laws for sample covariance and generalized Wigner matrices
• Limit laws for random matrices and free products
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• Limiting empirical singular value distribution of restrictions of discrete Fourier transform matrices
• Local semicircle law and complete delocalization for Wigner random matrices
• Local semicircle law for Wigner matrices
• Mean-field equations for spin models with orthogonal interaction matrices
• Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix
• Neural networks and physical systems with emergent collective computational abilities
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• On the distribution of the roots of certain symmetric matrices
• On the universality of noiseless linear estimation with respect to the measurement matrix
• Partitions ofN-Space by Hyperplanes
• Replica field theory for deterministic models. II. A non-random spin glass with glassy behaviour
• Several applications of the moment method in random matrix theory
• Spectral Method for Phase Retrieval: An Expectation Propagation Perspective
• State evolution for approximate message passing with non-separable functions
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Surprises in high-dimensional ridgeless least squares interpolation
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve
• The jackknife estimate of variance
• The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
• Universality in polytope phase transitions and message passing algorithms
• Universality in Sherrington-Kirkpatrick's spin glass model
• Universality of approximate message passing algorithms
• Vector Approximate Message Passing

Cited in

(14)

• Optimization algorithms for multi-species spherical spin glasses
• Universality of approximate message passing algorithms and tensor networks
• The replica-symmetric free energy for Ising spin glasses with orthogonally invariant couplings
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• Equilibria of large random Lotka-Volterra systems with vanishing species: a mathematical approach
• Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
• Linear operator approximate message passing (OpAMP)
• Causal effect estimation under network interference with mean-field methods
• Elliptic approximate message passing and an application to theoretical ecology
• Spectral estimators for structured generalized linear models via approximate message passing
• Entrywise dynamics and universality of general first order methods
• A leave-one-out approach to approximate message passing
• Differentially private learning beyond the classical dimensionality regime
• Universality of estimators for high-dimensional linear models with block dependency

This page was built for publication: Universality of approximate message passing with semirandom matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142946)