Sufficient Statistic Memory Approximate Message Passing
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. However, state evolution does not necessarily guarantee the
convergence of iterative algorithms. To solve the convergence problem of
AMP-type algorithms in principle, this paper proposes a memory AMP (MAMP) under
a sufficient statistic condition, named sufficient statistic MAMP (SS-MAMP). We
show that the covariance matrices of SS-MAMP are L-banded and convergent. Given
an arbitrary MAMP, we can construct the SS-MAMP by damping, which not only
ensures the convergence, but also preserves the orthogonality, i.e., its
dynamics can be correctly described by state evolution.