Convergence analysis of Gaussian belief propagation : from pairwise to high-order graphical models

Abstract

Gaussian belief propagation (BP) is a message-passing algorithm running on factor graphs for computing the marginal distributions of a high-dimensional Gaussian probability density function (PDF). Unfortunately, Gaussian BP is not guaranteed to converge in loopy graphs. Although there are a few existing conditions for determining the convergence of Gaussian BP, the understanding of convergence of Gaussian BP is far from complete. For example, the existing results are derived based on a certain pairwise factorization of the high-dimensional Gaussian PDF. It is not known if these results would hold under other factorizations. Furthermore, the physical meaning and relationships among these conditions are not well understood. To provide a more complete picture and new insights on the convergence behavior of Gaussian BP, this thesis presents the convergence analysis of Gaussian BP from several new perspectives.

First, the convergence of Gaussian BP is investigated from a fixed point perspective. In particular, the existence condition of fixed points of Gaussian BP is first established. Then, conditioned on the existence of fixed points of Gaussian BP, the convergence of outgoing messages propagating from variable nodes to factor nodes on a factor graph is analyzed. By focusing on the outgoing messages instead of the usually analyzed incoming messages, it is revealed that outgoing messages' precisions converge if and only if there exist fixed points for Gaussian BP, thus providing an elegant interpretation on the nature of convergence. On the other hand, to guarantee the convergence of outgoing messages' means, two sufficient conditions are derived. The relations between the convergence conditions of outgoing messages' parameters and those of incoming messages' parameters are also revealed.

Next, the convergence of Gaussian BP is analyzed under a general pairwise graphical model. The general pairwise factorization includes all the existing pairwise factorizations in Gaussian Markov random field (MRF) and pairwise linear Gaussian model as special cases. Upon the convergence analysis of general pairwise factorization, existing convergence conditions developed for a particular pairwise factorization are extended to any pairwise factorization. Moreover, the newly established link between pairwise Gaussian MRF and pairwise linear Gaussian model reveals an easily verifiable sufficient convergence condition in pairwise linear Gaussian model, which provides a unified criterion for assessing the convergence of Gaussian BP in multiple applications.

Finally, the convergence of Gaussian BP is analyzed for a general class of high-order graphical models. This new class of models extends the existing convex decomposition and finds extensive applications. In addition to the totally asynchronous scheduling, two new classes of schedulings, termed quasi-asynchronous scheduling, and independent and identically distributed (I.I.D.) quasi-asynchronous scheduling, are proposed. With their simpler structures, necessary and sufficient convergence conditions are derived. It is found that Gaussian BP under the I.I.D. quasi-asynchronous scheduling demonstrates better convergence than synchronous scheduling. This provides the potential of converting a non-convergent system into a convergent one, by choosing a proper message-passing schedule.(Total words: 484)