Reconciling AMP Algorithms derived from Belief Propagation or the Large System Limit Bethe Free Energy

Abstract

When derived from the Bethe Free Energy (BFE) of the Generalized Linear Model (GLM), Approximate Message Passing (AMP) algorithms combine two asymptotic Large System Limit (LSL) simplifications which are asymptotic Gaussianity of extrinsics and large random matrix theory based asymptotic variance computations. In the provably convergent AMBGAMP algorithm, a LSL version of the BFE is derived. In Expectation Propagation (EP) style minimization, the LSL BFE cost function is augmented with Lagrangian terms for mean and variance consistency constraints, augmented with a quadratic version of the mean constraints as in the Method of Multipliers (MM). The mean Lagrange multipliers then get updated ADMM-style (Alternating Direction of MM). In this approach, the weights of the MM terms need to be carefully chosen, which is not part of the MM philosophy, and the Lagrange multipliers have no particular meaning. On the other hand, AMP can be derived by directly introducing LSL simplifications in the Belief Propagtion (BP) algorithm that minimizes the original GLM BFE. This allows to relate extrinsic messages to posterior pdfs by first-order Taylor series expansion based perturbations. We also apply LSL approximations to the variances of the various Gaussians involved, which in fact leads to a rederivation of a fundamental LSL theorem describing the deterministic limit of posterior variances. We show that this LSL version of BP leads to BFE modifications that correspond to the augmented Lagrangian of the LSL BFE, explaining its weights and Lagrange Multipliers. These insights should facilitate the extension of AMP to more complex settings such as bilinear models.