On the Convergence of Approximate Message Passing With Arbitrary Matrices
On the Convergence of Approximate Message Passing With Arbitrary Matrices
复制标题
DOI：
10.1109/tit.2019.2913109
复制
发表时间：
2014-02
影响因子：
2.5
通讯作者：
S. Rangan;P. Schniter;A. Fletcher;Subrata Sarkar
中科院分区：
文献类型：
--
作者：
S. Rangan;P. Schniter;A. Fletcher;Subrata Sarkar
近似消息传递（AMP）方法及其变体引起了最近的关注，因为估计通过线性变换观察到的随机矢量X的问题A。在较大的I.I.D.中。零均值高斯A，该方法表现出快速收敛性，并在算法行为上具有精确的分析表征。但是，在一般变换A下的AMP的收敛尚未完全了解。在本文中，在二次成本函数（即高斯的可能性和先验）的情况下，我们提供了足够的条件，以使其融合版本的广义AMP（GAMP）算法的收敛性提供足够的条件。结果表明，尽管有足够的阻尼，算法可以保证会融合，尽管阻尼的量增长，而变换的平方奇异值的峰值与平均值的比率则是A。该结果解释了AMP在I.I.D上的良好性能。高斯转换A，但在不良条件或非零均值转换A的困难A。
Approximate message passing (AMP) methods and their variants have attracted considerable recent attention for the problem of estimating a random vector x observed through a linear transform A. In the case of large i.i.d. zero-mean Gaussian A, the methods exhibit fast convergence with precise analytic characterizations on the algorithm behavior. However, the convergence of AMP under general transforms A is not fully understood. In this paper, we provide sufficient conditions for the convergence of a damped version of the generalized AMP (GAMP) algorithm in the case of quadratic cost functions (i.e., Gaussian likelihood and prior). It is shown that, with sufficient damping, the algorithm is guaranteed to converge, although the amount of damping grows with peak-to-average ratio of the squared singular values of the transforms A. This result explains the good performance of AMP on i.i.d. Gaussian transforms A, but also their difficulties with ill-conditioned or non-zero-mean transforms A. A related sufficient condition is then derived for the local stability of the damped GAMP method under general cost functions, assuming certain strict convexity conditions.