On the Convergence of Approximate Message Passing With Arbitrary Matrices

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 analyti...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2019-09, Vol.65 (9), p.5339-5351
Main Authors: Rangan, Sundeep, Schniter, Philip, Fletcher, Alyson K., Sarkar, Subrata
Format: Article
Language:English
Subjects:
Algorithms
Approximate message passing
Approximation
Belief propagation
Conditioning
Convergence
Convexity
Cost function
Damping
Economic models
Estimation
Gaussian belief propagation
Linear transformations
loopy belief propagation
Message passing
primal-dual algorithms
Probability density function
Transforms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2019.2913109