Non-asymptotic bounds for approximate message passing via Gaussian coupling

Approximate message passing (AMP) has emerged as a powerful framework for the design and analysis of iterative algorithms for high dimensional inference problems involving regression and low-rank matrix factorization. The basic form of an AMP algorithm consists of a recursion defined on a random matrix. Under suitable conditions, the distribution of this recursion can be well approximated by a Gaussian process whose mean and covariance are defined via a recursive process called state evolution. This talk will briefly summarize some of the key ideas in AMP (no background is assumed). I will then describe a new approach for analyzing these algorithms that constructs an explicit coupling between the AMP iterates and a Gaussian process, Under mild regularity conditions, this coupling argument provides simple and interpretable guarantees on the non-asymptotic behavior of AMP algorithms. Related work can be found in the arXiv papers: https://arxiv.org/abs/2405.08225 and https://arxiv.org/abs/2306.15580