Convergent Approximate Message Passing by Alternating Constrained Minimization of Bethe Free Energy

Approximate Message Passing (AMP) allows for Bayesian inference in linear models with non identically independently distributed (n.i.i.d.) Gaussian priors and measurements of the linear mixture outputs with n.i.i.d. Gaussian noise. 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. It has been shown that the fixed points of AMP correspond to extrema of a large system limit of the Bethe Free Energy (LSL-BFE), which represents a meaningful approximation optimization criterion regardless of whether the measurement matrix exhibits the independence properties. However, the convergence of AMP can be notoriously problematic for certain measurement matrices and the only sure fix so far is damping (by a difficult to determine amount). In this paper we revisit the AMP algorithm by rigorously applying an alternating constrained minimization strategy to an appropriately reparameterized LSL-BFE with matched variable and constraint partitioning. This guarantees convergence, and due to convexity in the Gaussian case, to the global optimum. We show that the AMP estimates converge to the Linear Minimum Mean Squared Error (LMMSE) estimates, regardless of the behavior of the variances. In the LSL, the variances also converge to the LMMSE values, and hence to the correct values.