Fixed Points of Generalized Approximate Message Passing With Arbitrary Matrices

DOI10.1109/TIT.2016.2619365MaRDI QIDQ2976466zbMATH OpenFDO

Authors Sundeep Rangan, Philip Schniter, Erwin Riegler, Alyson K. Fletcher, Volkan Cevher

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6295

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: 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 free energy.

Cited in

(13)

• Approximate message passing algorithms for rotationally invariant matrices
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Approximate survey propagation for statistical inference
• scientific article; zbMATH DE number 7625169 (Why is no real title available?)
• Denoising AMP for MRI reconstruction: BM3D-AMP-MRI
• A Unifying Tutorial on Approximate Message Passing
• A tradeoff between false discovery and true positive proportions for sparse high-dimensional logistic regression
• High-Dimensional Macroeconomic Forecasting Using Message Passing Algorithms
• High-dimensional learning of narrow neural networks
• Equivalence of state equations from different methods in high-dimensional regression
• A phase transition between positional and semantic learning in a solvable model of dot-product attention
• Moment-based adjustments of statistical inference in high-dimensional generalized linear models
• The nuclear route: sharp asymptotics of ERM in overparameterized quadratic networks

This page was built for publication: Fixed Points of Generalized Approximate Message Passing With Arbitrary Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976466)