GaBP

GaBP stands for Gaussian Belief Propagation. It is a message-passing algorithm for performing probabilistic inference in Gaussian graphical models. In GaBP, variables are continuous and joint distributions are Gaussian, so all messages and marginals are Gaussian. This allows efficient computation of marginal means and variances and, in some formulations, can be used to solve linear systems by interpreting the system as a Gaussian Markov random field.

Algorithm Overview: The model is represented as a factor graph with variable nodes and factor nodes. Messages between nodes summarize belief as a Gaussian with precision (inverse variance) and a mean. Each update combines the prior, likelihood, and incoming messages to produce outgoing messages; the algorithm iterates until marginal estimates converge or a stopping criterion is met. On acyclic graphs the estimates are exact; on graphs with cycles they converge approximately under certain conditions.

Convergence and Practicality: GaBP is particularly attractive for distributed and parallel computation because each node only exchanges local messages. It is well-suited for sparse systems and can be used to solve linear systems by running GaBP to obtain x approximating A^{-1}b; under certain conditions the resulting x converges to the true solution. In loopy graphs, convergence is not guaranteed, and damping or scheduling strategies are commonly employed.

Applications and Relation: It has been applied in sensor networks, computer vision, communications, and statistics. GaBP is a specialization of belief propagation to Gaussian models, closely related to solving linear systems via iterative message passing and to graphical model inference in continuous domains.