A demonstration of the reweighted Gaussian belief propagation algorithm.

Matrix Settings

Matrix Properties

Matrix Size = 5

Belief Propagation Settings

Initialization

Simulation Speed

Reweighting Parameter (c) = 15

Error: Estimated Minimum:

Description

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!