Gaussian Belief Propagation

A demonstration of the reweighted Gaussian belief propagation algorithm.
Matrix Settings
Matrix Properties
Matrix Size = 5
Belief Propagation Settings
Simulation Speed
Reweighting Parameter (c) = 15
Estimated Minimum:


The above is a demonstration of the Gaussian belief propagation (GaBP) algorithm with a reweighted message passing scheme. The GaBP algorithm is an iterative message-passing scheme that attempts to solve the linear system \(Ax = b\) for the vector \(x\) or, equivalently, GaBP attempts to minimize the quadratic \(-1/2x'Ax - h'x\). Observe that for sufficiently large choices of the reweighting parameter, \(c\), the computation trees produced by the algorithm are positive definite and the message updates are well-defined. When \(c = 1\), and the matrix is scaled diagonally dominant (equivalently, walk-summable), then the algorithm always converges.

About This Demo

This demonstration was created for HTML 5 capable browsers (needs canvas support) by Nicholas Ruozzi. While I cannot gurantee that the code is error free, feel free to download the source code for this demonstration and use/modify/improve it!