论文标题
关于大约消息传递的简明教程
A Concise Tutorial on Approximate Message Passing
论文作者
论文摘要
标准线性回归的高维信号恢复是许多工程领域的关键挑战，例如通信，压缩传感和图像处理。 Donoho \ textit {et al}提出的近似消息传递（AMP）算法是解决此类问题的计算有效方法，可以在独立相同的分布式（IID）亚高斯随机矩阵区域中达到贝叶斯最佳性能。 AMP的一个重要特征是，可以通过称为站点进化的标量方程（SE）充分预测AMP的动力学行为。尽管AMP在IID次高斯随机矩阵中是最佳的，但是当测量矩阵超出IID亚高斯时，AMP可能无法收敛。为了扩展随机测量矩阵的区域，提出了期望传播（EP）相关算法正交AMP（OAMP），该算法（OAMP）与EP共享相同的算法，期望一致（EC）和载体AMP（VAMP）。本文旨在对这些算法进行审查。我们从最坏的情况开始，即最少绝对的收缩和选择运算符（LASSO）推断问题，然后给出从消息传递中得出的AMP的详细推导。同样，在贝叶斯最佳环境中，我们给出了贝叶斯最佳的放大器，该放大器与lasso的AMP略有差异。此外，我们回顾了一些与AMP相关的算法：OAMP，VAMP和内存AMP（MAMP），可以应用于更通用的随机矩阵。
High-dimensional signal recovery of standard linear regression is a key challenge in many engineering fields, such as, communications, compressed sensing, and image processing. The approximate message passing (AMP) algorithm proposed by Donoho \textit{et al} is a computational efficient method to such problems, which can attain Bayes-optimal performance in independent identical distributed (IID) sub-Gaussian random matrices region. A significant feature of AMP is that the dynamical behavior of AMP can be fully predicted by a scalar equation termed station evolution (SE). Although AMP is optimal in IID sub-Gaussian random matrices, AMP may fail to converge when measurement matrix is beyond IID sub-Gaussian. To extend the region of random measurement matrix, an expectation propagation (EP)-related algorithm orthogonal AMP (OAMP) was proposed, which shares the same algorithm with EP, expectation consistent (EC), and vector AMP (VAMP). This paper aims at giving a review for those algorithms. We begin with the worst case, i.e., least absolute shrinkage and selection operator (LASSO) inference problem, and then give the detailed derivation of AMP derived from message passing. Also, in the Bayes-optimal setting, we give the Bayes-optimal AMP which has a slight difference from AMP for LASSO. In addition, we review some AMP-related algorithms: OAMP, VAMP, and Memory AMP (MAMP), which can be applied to more general random matrices.
