Universality of Approximate Message Passing with Semi-Random Matrices

Understand

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 $\mathbf{M}$.
• Theoretical analyses of AMP typically assume strong distributional properties on $\mathbf{M}$ such as $\mathbf{M}$ has i.i.d.
• sub-Gaussian entries or is drawn from a rotational invariant ensemble.