Memory AMP

• Published in: IEEE transactions on information theory 2022-12, Vol.68 (12), p.8015-8039
• Main Authors: Liu, Lei, Huang, Shunqi, Kurkoski, Brian M.
• Format: Article
• Language: English
• Subjects: Approximate message passing (AMP); Asymptotic properties; Bayes optimality; Complexity; Complexity theory; compressed sensing; Convergence; Damping; Estimation error; Evolution; Invariants; large system limit; Linear systems; low complexity; Matched filters; Mathematical analysis; Matrices (mathematics); memory AMP; Message passing; orthogonal/vector AMP; Orthogonality; Parameter estimation; right-unitarily invariant; Sparse matrices; state evolution
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2022.3186166

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable (e.g., perform poorly or even diverge) for other matrix ensembles, especially for ill-conditioned ones. To solve this issue, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP (BO-OAMP/VAMP) requires a high-complexity linear minimum mean square error (MMSE) estimator. This prevents OAMP/VAMP from being used in large-scale systems. To address the drawbacks of AMP and BO-OAMP/VAMP, this paper offers a memory AMP (MAMP) framework based on the orthogonality principle, which ensures that estimation errors in MAMP are asymptotically IID Gaussian. To realize the required orthogonality for MAMP, we provide an orthogonalization procedure for the local memory estimators. In addition, we propose a Bayes-optimal MAMP (BO-MAMP), in which a long-memory matched filter is used for interference suppression. The complexity of BO-MAMP is comparable to AMP. To asymptotically characterize the performance of BO-MAMP, a state evolution is derived. The relaxation parameters and damping vector in BO-MAMP are optimized based on state evolution. Most crucially, the state evolution of the optimized BO-MAMP converges to the same fixed point as that of the high-complexity BO-OAMP/VAMP for all right-unitarily-invariant matrices, and achieves the Bayes optimal MSE predicted by the replica method if its state evolution has a unique fixed point. Finally, simulations are provided to verify the theoretical results' validity and accuracy.