Ferkans — Interactive Telecom Tutor

When Messages Are Gaussians

Sum-product on discrete variables computes probability tables. For continuous variables the analog is densities — but general densities are infinite-dimensional. The algorithm becomes computationally heavy.

There is one continuous family where sum-product remains tractable: jointly Gaussian distributions. In this case, every message is itself a Gaussian density, parameterized by a mean (or precision) vector and a covariance (or precision) matrix. The message updates are finite matrix operations. This yields Gaussian belief propagation (GaBP) — the continuous analog of LDPC decoding.

The point of this section is that GaBP is the right tool whenever the model is (approximately) jointly Gaussian: iterative MIMO detection, Kalman filtering on a tree-structured state space, distributed least-squares estimation. It plugs into iterative receivers where soft outputs are needed in real time.

Definition:
Gaussian Factor Graph

A Gaussian factor graph has each factor of the form $f_a(\mathbf{x}_{\partial a}) = \exp\!\left(-\tfrac{1}{2}\mathbf{x}_{\partial a}^T \mathbf{J}_a \mathbf{x}_{\partial a} + \mathbf{h}_a^T \mathbf{x}_{\partial a}\right),$ where $\mathbf{J}_a \succeq 0$ (information / precision) and $\mathbf{h}_a$ (potential) are the canonical parameters. The global distribution $p(\mathbf{x}) \propto \prod_a f_a$ is then the multivariate Gaussian with total precision $\mathbf{J} = \sum_a \mathbf{J}_a$ (appropriately padded) and potential $\mathbf{h} = \sum_a \mathbf{h}_a$ . The marginals $p(x_i)$ are Gaussian with mean $\mu_i = (\mathbf{J}^{-1}\mathbf{h})_i$ and variance $\sigma_i^2 = (\mathbf{J}^{-1})_{ii}$ .

The information form $(\mathbf{h}, \mathbf{J})$ is the natural parameterization for message passing — products of Gaussians are computed by adding information parameters, and marginalization requires a matrix inversion that reduces nicely for tree-structured graphs.

Theorem: Gaussian BP Update Rules

For a pairwise Gaussian factor graph with factors $f_{ij}(x_i, x_j) \propto \exp(-\tfrac{1}{2}[x_i, x_j] \mathbf{J}_{ij} [x_i, x_j]^T)$ and unary terms $f_i(x_i) \propto \exp(-\tfrac{1}{2} J_{ii} x_i^2 + h_i x_i)$ , the Gaussian BP messages are parameterized as $\mu_{i \to j}(x_j) \propto \exp(-\tfrac{1}{2} J_{i \to j} x_j^2 + h_{i \to j} x_j)$ with updates $J_{i \to j} = -(J_{ij,12})^2 / (J_{ii} + \sum_{k \in \partial i \setminus j} J_{k \to i} + J_{ij,11}),$ $h_{i \to j} = -J_{ij,12}(h_i + \sum_{k \neq j} h_{k \to i}) / (J_{ii} + \ldots + J_{ij,11}).$ The final belief at node $i$ is Gaussian with precision $J_i^\star = J_{ii} + \sum_{k \in \partial i} J_{k \to i}$ and potential $h_i^\star = h_i + \sum_k h_{k \to i}$ .

GaBP parameterizes messages by scalar precision and potential pairs (for pairwise factors). Products of Gaussians are Gaussians whose parameters add; marginalization of a jointly-Gaussian pair is Schur-complement computation. Every message update is $O(1)$ , and the whole algorithm runs at matrix-inversion-level speed without ever forming an inverse.

Proof

Parameterize Gaussian messages

A Gaussian message in $x$ has the form $\exp(-\tfrac{1}{2}Jx^2 + hx)$ , parameterized by $(h, J)$ . Products of such messages: $(h_1, J_1) \cdot (h_2, J_2) = (h_1 + h_2, J_1 + J_2)$ .

Marginalization via Schur complement

For a pairwise factor $\exp(-\tfrac{1}{2}[\mathbf{x}] \mathbf{J} [\mathbf{x}]^T + \mathbf{h}^T[\mathbf{x}])$ , integrating out one variable gives a Gaussian in the other with precision $J_{11} - J_{12}^2/J_{22}$ and potential appropriately transformed.

Combine to get BP update

Apply the sum-product rule for the factor-to-variable message, multiply the incoming messages on the eliminated side, and marginalize. The formulas are the result.

Convergence condition

GaBP converges when the precision matrix $\mathbf{J}$ is walk-summable, e.g., diagonally dominant. This is a widely applicable but strict condition.

, ,

Theorem: Means Are Always Correct for GaBP

If GaBP converges on a Gaussian graph with precision matrix $\mathbf{J}$ , the computed means $\mu_i^\star = h_i^\star / J_i^\star$ equal the exact Gaussian marginal means $(\mathbf{J}^{-1}\mathbf{h})_i$ , regardless of whether the graph is a tree. The variances $(J_i^\star)^{-1}$ may differ from the true marginal variances $(\mathbf{J}^{-1})_{ii}$ .

This is a striking property: loopy GaBP is still correct for point estimates, even though it makes errors in uncertainty quantification. The means behave as though the graph were a tree because they solve a linear fixed-point system equivalent to the true linear system. The variances, in contrast, depend on global cycle structure that loopy BP cannot capture correctly.

Proof

Fixed-point equations are linear

Upon convergence, the GaBP potential messages $\{h_{k \to i}\}$ satisfy a linear fixed-point system arising from the BP update rules.

Equivalence to $\mathbf{J}\boldsymbol{\mu} = \mathbf{h}$

One verifies (by direct substitution) that the computed means $\mu_i^\star$ satisfy $\mathbf{J}\boldsymbol{\mu}^\star = \mathbf{h}$ — precisely the system that characterizes the true Gaussian mean.

Variances miss cycle contributions

The variance estimate $(J_i^\star)^{-1}$ is based on a walk-sum expansion that includes only walks with no backtracking; actual $(\mathbf{J}^{-1})_{ii}$ includes all walks. Cycles contribute discounted corrections that GaBP misses.

,

Gaussian Belief Propagation (Pairwise)

Complexity:

O(|\mathcal{E}|)

per iteration (one scalar update per edge). Total memory:

O(|\mathcal{E}|)

. Compare to direct matrix inversion

O(N^3)

— GaBP is exponentially cheaper for sparse

\mathbf{J}

.

Input: pairwise Gaussian precision matrix J, potential vector h, max iterations T

Output: beliefs (mu_i, var_i) for each node

// Initialize messages

for each edge (i, j):

J_{i->j} = 0

h_{i->j} = 0

for t = 1 to T:

for each edge (i, j):

// Compute aggregate incoming at i (excluding j)

J_i_agg = J[i,i] + sum over k in N(i){j}: J_{k->i}

h_i_agg = h[i] + sum over k in N(i){j}: h_{k->i}

// Marginalize out x_i from the pairwise factor f_{ij}

J_{i->j} = -(J[i,j])^2 / J_i_agg

h_{i->j} = -J[i,j] * h_i_agg / J_i_agg

// Beliefs

for each node i:

J_star[i] = J[i,i] + sum over k in N(i): J_{k->i}

h_star[i] = h[i] + sum over k in N(i): h_{k->i}

mu[i] = h_star[i] / J_star[i]

var[i] = 1 / J_star[i]

return (mu, var)

Walk-summable $\mathbf{J}$ (diagonally dominant) guarantees convergence. In practice, damping messages (take a convex combination of old and new) extends the convergence range.

Example: GaBP on a 3-Node Cycle

Solve the linear system $\mathbf{J}\boldsymbol{\mu} = \mathbf{h}$ with $\mathbf{J} = \begin{pmatrix} 4 & 1 & 1 \\ 1 & 4 & 1 \\ 1 & 1 & 4 \end{pmatrix}$ and $\mathbf{h} = (1, 2, 3)^T$ using GaBP. Compare to the exact solution.

Solution

Exact solution

$\mathbf{J}^{-1} = \frac{1}{42}\begin{pmatrix} 15 & -3 & -3 \\ -3 & 15 & -3 \\ -3 & -3 & 15 \end{pmatrix}$ , so $\boldsymbol{\mu}^\star = \frac{1}{42}(15 - 6 - 9, -3 + 30 - 9, -3 - 6 + 45) = \frac{1}{42}(0, 18, 36) = (0, 3/7, 6/7)$ .

Set up GaBP

Pairwise factors: $J_{ij} = 1$ for $i \neq j$ ; diagonal $J_{ii} = 4$ . All three pairwise edges. The graph is a 3-cycle.

Run iterations

Initialize $J_{k \to i} = 0, h_{k \to i} = 0$ . Iterate until convergence. After ~20 iterations, $\boldsymbol{\mu}^\star_{\text{GaBP}} \to (0, 3/7, 6/7)$ — exactly matches the true means, despite the cycle.

Variances differ

True variances: $(\mathbf{J}^{-1})_{ii} = 15/42 \approx 0.357$ . GaBP variance estimate: $(J_i^\star)^{-1} \approx 0.33$ — slightly off. This illustrates the theorem: means exact, variances approximate.

Why This Matters: GaBP for MIMO Detection

For a MIMO receiver with dense channel matrix $\mathbf{H}$ , exact MMSE detection requires inverting $\mathbf{H}^H\mathbf{H} + \sigma^2\mathbf{I}$ — cubic in the number of streams. GaBP on the factor graph of the posterior gives MMSE estimates (means) with iteration complexity linear in $\mathbf{H}$ 's non-zeros. For sparse or banded channels (ISI, massive MIMO with sparse beamspace representation), this delivers orders of magnitude speedup. 5G terminal MIMO receivers often use a GaBP-based inner loop coupled with an LDPC outer decoder.

GaBP Convergence: Diagonal Dominance Matters

Show GaBP convergence on random sparse Gaussian graphs. Vary the diagonal dominance factor and observe convergence vs. divergence.

Parameters

Number of nodes

N

20

Edge density0.2

Diagonal dominance factor1.5

Common Mistake: GaBP Divergence from Weak Diagonal Dominance

Mistake:

Running GaBP on a precision matrix with $J_{ii} \leq \sum_{j \neq i} |J_{ij}|$ (fails strict diagonal dominance) and assuming it will converge.

Correction:

GaBP is guaranteed to converge only when $\mathbf{J}$ is walk-summable (implied by strict diagonal dominance). For weakly diagonally dominant or indefinite matrices, add damping: $m^{(t+1)} = \gamma m^{(t)} + (1-\gamma) m^{(t+1),\text{new}}$ , with $\gamma \in [0.3, 0.7]$ . In adversarial cases (e.g., MIMO with coherent channels), fall back to direct solvers.

🔧Engineering Note

GaBP in Silicon

GaBP's scalar message updates map cleanly to parallel hardware: each edge's update is independent within a layer. Commercial 5G receivers implement GaBP with damping factor 0.5 and 5-10 iterations, achieving within 0.5 dB of exact MMSE at a fraction of the matrix-inversion latency.

Practical Constraints

•
Precision required: ~12 bits to avoid variance drift.
•
Walk-summability checked offline; online diagnostic monitors divergence.
•
Typical convergence in 5-15 iterations for MIMO detection.

🎓CommIT Contribution(2018)

Approximate Gaussian BP for Massive MIMO

C. Jeon, R. Ghods, C. Studer, G. Caire — Proc. IEEE SPAWC

The CommIT group and collaborators have developed GaBP-based MIMO detection algorithms tailored for massive MIMO uplink. These algorithms combine GaBP with deterministic-equivalent regularization (Chapter 16) to achieve near-MMSE performance with hardware-friendly complexity.

Gaussian BPMIMO detectionmassive MIMO

Quick Check

GaBP is run on a loopy Gaussian graph and converges. What can we say about the computed means and variances?

Means exact, variances approximate

Both means and variances exact

Both means and variances approximate

Neither (GaBP cannot handle loops)

Correction:

Means exact, variances approximate

This is the key theorem: the means solve $\mathbf{J}\boldsymbol{\mu}=\mathbf{h}$ exactly, but variances miss cycle contributions.

Key Takeaway

Gaussian belief propagation is sum-product specialized to jointly Gaussian distributions. Messages are Gaussian densities parameterized by information form $(h, J)$ ; products add, marginalization is Schur-complement. On any convergent graph (including loopy ones), the means are exact — variances are approximate. GaBP is the workhorse for iterative MIMO detection and large-scale sparse linear system solving.

Gaussian Belief Propagation

When Messages Are Gaussians

Definition: Gaussian Factor Graph

Theorem: Gaussian BP Update Rules

Parameterize Gaussian messages

Marginalization via Schur complement

Combine to get BP update

Convergence condition

Theorem: Means Are Always Correct for GaBP

Fixed-point equations are linear

Equivalence to $\mathbf{J}\boldsymbol{\mu} = \mathbf{h}$

Variances miss cycle contributions

Gaussian Belief Propagation (Pairwise)

Example: GaBP on a 3-Node Cycle

Exact solution

Set up GaBP

Run iterations

Variances differ

Why This Matters: GaBP for MIMO Detection

GaBP Convergence: Diagonal Dominance Matters

Parameters

Common Mistake: GaBP Divergence from Weak Diagonal Dominance

GaBP in Silicon

Approximate Gaussian BP for Massive MIMO

Quick Check

Key Takeaway

Definition:
Gaussian Factor Graph