Extrinsics and Linearized Component-Wise Conditionally Unbiased MMSE Estimation in Approximate Message Passing
Zilu Zhao, Dirk T. M. Slock · 2025
The Bethe Free Energy (BFE) has been found to be closely connected to various message passing algorithms. Studies have indicated that the BFE shares stationary points with message passing algorithms like Belief Propagation (BP) and Expectation Propagation (EP). Generalized Approximate Message Passing (GAMP) algorithms have demonstrated significant efficacy in signal recovery. Nevertheless, they may encounter convergence issues. EP algorithms start from a factored approximate posterior in an exponential family. They update a factor by fitting an exponential family pdf to a approximate posterior which is obtained by replacing one approximate factor by the original (prior) factor. The remaining factors form the approximate extrinsic. Hence extrinsics are obtained by marginalizing the product of all pdf factors except for the prior. A marginal posterior is then obtained by combining the extrinsic with the prior. Low complexity algorithms like GAMP in turn obtain the extrinsic from the posterior. In this paper, we explore the BFE within the context of Generalized Linear Models (GLMs). Applying a BFE based EP approach leads to the re(G)VAMP algorithm which provides asymptotically exact marginal posteriors based on asymptotically Gaussian extrinsics. It also provides equivalent Gaussian priors and hence an equivalent overall Gaussian linear model, which allows the application of large random matrix theory. We show how on the other hand how Large System Limit (LSL) based approximations in BP lead to GAMP. When derived from the BFE of the GLM, GAMP algorithms combine two asymptotic LSL simplifications which are asymptotic Gaussianity of extrinsics and large random matrix theory based asymptotic variance computations. The LSL simplifications allow 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. These insights should facilitate the extension of AMP to more complex settings such as bilinear models.