# Sufficient-Statistic Memory AMP

arXiv: https://arxiv.org/abs/2112.15327 · HTML: https://mlsanity.com/paper/2112.15327/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 60 references that are in the map.
- First posted on arXiv 31 Dec 2021.

## Builds on (most cited first, 12 of 12)

- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020)
- [Generalization Error of Generalized Linear Models in High Dimensions](https://mlsanity.com/paper/2005.00180/) (2020)
- [Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)](https://mlsanity.com/paper/2006.06581/) (2020)
- [Phase transitions and sample complexity in Bayes-optimal matrix factorization](https://mlsanity.com/paper/1402.1298/) (2014)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [Inference with Deep Generative Priors in High Dimensions](https://mlsanity.com/paper/1911.03409/) (2019)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [Multi-Layer Generalized Linear Estimation](https://mlsanity.com/paper/1701.06981/) (2017)
- [Memory AMP](https://mlsanity.com/paper/2012.10861/) (2020)
- [Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding](https://mlsanity.com/paper/1501.05892/) (2015)
- [Memory Approximate Message Passing](https://mlsanity.com/paper/2106.02237/) (2021)

## Built on by (most cited first, 2 of 2)

- [Sufficient Statistic Memory Approximate Message Passing](https://mlsanity.com/paper/2206.11674/) (2022)
- [Capacity Optimality of OAMP in Coded Large Unitarily Invariant Systems](https://mlsanity.com/paper/2206.11680/) (2022)

## Abstract (arXiv)

Approximate message passing (AMP) type algorithms have been widely used in the signal reconstruction of certain large random linear systems. A key feature of the AMP-type algorithms is that their dynamics can be correctly described by state evolution. While state evolution is a useful analytic tool, its convergence is not guaranteed. To solve the convergence problem of the state evolution of AMP-type algorithms in principle, this paper proposes a sufficient-statistic memory AMP (SS-MAMP) algorithm framework under the conditions of right-unitarily invariant sensing matrices, Lipschitz-continuous local processors and the sufficient-statistic constraint (i.e., the current message of each local processor is a sufficient statistic of the signal vector given the current and all preceding messages). We show that the covariance matrices of SS-MAMP are L-banded and convergent, which is an optimal framework (from the local MMSE/LMMSE perspective) for AMP-type algorithms given the Lipschitz-continuous local processors. Given an arbitrary MAMP, we can construct an SS-MAMP by damping, which not only ensures the convergence of the state evolution, but also preserves the orthogonality, i.e., its dynamics can be correctly described by state evolution. As a byproduct, we prove that the Bayes-optimal orthogonal/vector AMP (BO-OAMP/VAMP) is an SS-MAMP. As an example, we construct a sufficient-statistic Bayes-optimal MAMP (SS-BO-MAMP) whose state evolution converges to the minimum (i.e., Bayes-optimal) mean square error (MSE) predicted by replica methods when it has a unique fixed point. In addition, the MSE of SS-BO-MAMP is not worse than the original BO-MAMP. Finally, simulations are provided to support the theoretical results.