On convergence and accuracy of Gaussian belief propagation

Abstract

Gaussian belief propagation (BP) is known to be an efficient message-passing algorithm for calculating approximate marginal probability density function (PDF) from a high dimensional Gaussian PDF. When Gaussian BP converges, it is known that the mean calculated by Gaussian BP (Gaussian BP mean) is the mean of exact marginal PDF, while the variance calculated by Gaussian BP (Gaussian BP variance) is an approximation to the variance of exact marginal PDF. Since Gaussian BP is not guaranteed to converge, it is important to know under what conditions Gaussian BP converges. Moreover, due to the unknown accuracy of Gaussian BP variance, it is also meaningful to analyze and improve its accuracy. In this thesis, the issues of convergence and accuracy in Gaussian BP are focused on.

First, the convergence condition of Gaussian BP variances is investigated. In particular, by analyzing the message updating functions of Gaussian BP, the necessary and sufficient convergence condition of Gaussian BP variances is derived under both synchronous and asynchronous schedulings. The relationship between the proposed convergence condition and the existing one is also established analytically. Comparing to the existing best convergence condition which is sufficient only and requires computing the spectral radius of an infinite dimensional matrix, the proposed condition not only fills in the necessary part of the existing condition, but also can be verified efficiently.

Next, based on the convergence condition of Gaussian BP variances, the necessary and sufficient convergence conditions of beliefs (parameterized by Gaussian BP variance and mean) are derived in the scenarios of synchronous scheduling with or without damping. The results theoretically confirm the extensively reported conjecture that damping is helpful to improve the convergence of Gaussian BP. Under asynchronous scheduling, a sufficient convergence condition of beliefs is also derived. Relationships between the proposed convergence conditions and existing ones are established analytically, demonstrating that the existing conditions are implied by the proposed ones.

Finally, the accuracy of Gaussian BP variances is analyzed and improved. In particular, an explicit error expression of Gaussian BP variances is first derived. By novel representation of this error expression, a distributed message-passing algorithm is proposed to improve the accuracy of Gaussian BP variance. It is proved that the upper bound of the residual error in the improved variance monotonically decreases as the number of nodes in a particular set increases, and eventually vanishes to zero as the remaining graph becomes loop-free after removal of the selected nodes.