Universality of Approximate Message Passing Algorithms

Abstract

We consider a broad class of Approximate Message Passing (AMP) algorithms defined as a Lipschitzian functional iteration in terms of an $n\times n$ random symmetric matrix $A$. We establish universality in noise for this AMP in the $n$-limit and validate this behavior in a number of AMPs popularly adapted in compressed sensing, statistical inferences, and optimizations in spin glasses.

arXiv comment43 pages, minor revision in the introduction

References in corpus (8)

• Message Passing Algorithms for Compressed Sensing
• Bilinear Generalized Approximate Message Passing
• Universality in polytope phase transitions and message passing algorithms
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Mutual Information in Rank-One Matrix Estimation