Gaussian BP on trees


Marginalization in Gaussian MRFs can be performed in cubic time by inverting a matrix, but this is too slow for some applications. If the model is tree-structured, belief propagation can compute the means and single-node variances in linear time. Unlike in general MRFs, it turns out that the loopy version yields the correct means.


This concept has the prerequisites:

Core resources (we're sorry, we haven't finished tracking down resources for this concept yet)

Supplemental resources (the following are optional, but you may find them useful)


Walk-sums and belief propagation in Gaussian graphical models
Location: Section 2.2, up to "Loopy belief propagation"
Authors: Dmitry M. Malioutov,Jason K. Johnson,Alan S. Willsky
Gaussian Belief Propagation: Theory and Application
Location: Section 2, pages 8-16
Author: Danny Bickson


See also

  • If we apply the same update rules on a non-tree graph, it often works just fine. This is known as loopy belief propagation .