Accelerated generalized approximate message passing

Generalized Approximate Message Passing (GAMP) enables Bayesian inference in linear models with non-identically and independently distributed (n.i.i.d.) priors and n.i.i.d. measurements of the linear mixture outputs. It represents an efficient technique for approximate inference, which becomes accurate when both rows and columns of the measurement matrix can be treated as sets of independent vectors and both dimensions

become large. The fixed points of GAMP correspond to the extrema of a large system limit of the Bethe Free Energy (LSLBFE), which represents a meaningful approximation criterion regardless of whether the measurement matrix exhibits the independence properties. However, the convergence of (G)AMP can be problematic for certain measurement matrices. In this paper, we revisit the LSL-BFE and its Lagrangian function. We derive an augmented GAMP algorithm by alternately enforcing the Karush-Kuhn-Tucker (KKT) conditions, called KKT-GAMP (KGAMP). To avoid matrix inversions, we introduce Adaptive (Accelerated) Gradient Descent (A(A)GD) techniques. Analysis

shows convergence under relaxed conditions. Simulations indicate accelerated convergence compared to existing low complexity methods and illustrate the importance of adaptation.