S. Rangan, P. Schniter, E. Riegler, A. Fletcher, V. Cevher:

"Fixed points of generalized approximate message passing with arbitrary matrices";

Talk: IEEE International Symposium on Information Theory (ISIT), Istanbul; 07-07-2013 - 07-12-2013; in: "Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on", (2013), 664 - 668.

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method

to more common optimization techniques. This analysis enables

a precise characterization of the GAMP algorithm fixed-points

that applies to arbitrary transforms. In particular, we show that

the fixed points of the so-called max-sum GAMP algorithm for

MAP estimation are critical points of a constrained maximization

of the posterior density. The fixed-points of the sum-product

GAMP algorithm for estimation of the posterior marginals can

be interpreted as critical points of a certain mean-field variational

optimization.

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method

to more common optimization techniques. This analysis enables

a precise characterization of the GAMP algorithm fixed-points

that applies to arbitrary transforms. In particular, we show that

the fixed points of the so-called max-sum GAMP algorithm for

MAP estimation are critical points of a constrained maximization

of the posterior density. The fixed-points of the sum-product

GAMP algorithm for estimation of the posterior marginals can

be interpreted as critical points of a certain mean-field variational

optimization.

http://dx.doi.org/10.1109/ISIT.2013.6620309

http://publik.tuwien.ac.at/files/PubDat_226360.pdf

Created from the Publication Database of the Vienna University of Technology.