On Convergence Rate of the Gaussian Belief Propagation Algorithm for Markov Networks
This work is incremental, improving theoretical understanding for researchers in signal processing and statistical learning.
The paper tackles the problem of analyzing the convergence rate of the Gaussian Belief Propagation algorithm for Markov networks, showing that under walk summability conditions, convergence is exponential and providing a simple bound for the rate.
Gaussian Belief Propagation (BP) algorithm is one of the most important distributed algorithms in signal processing and statistical learning involving Markov networks. It is well known that the algorithm correctly computes marginal density functions from a high dimensional joint density function over a Markov network in a finite number of iterations when the underlying Gaussian graph is acyclic. It is also known more recently that the algorithm produces correct marginal means asymptotically for cyclic Gaussian graphs under the condition of walk summability. This paper extends this convergence result further by showing that the convergence is exponential under the walk summability condition, and provides a simple bound for the convergence rate.