Core 11 min 2 of 3

Factor graphs and sparsity

Draw the graph and you have drawn the matrix. Eliminate a variable and you can see what it costs.

What this repairs

Treating the factor graph as a diagram for papers, rather than as a literal picture of the linear algebra.

Assumes

What SLAM is estimating

A factor graph is bipartite: variable nodes (poses, landmarks, calibration parameters, biases) and factor nodes (measurements, priors), with an edge wherever a factor depends on a variable. The posterior is the product of the factors, and the negative log posterior is the sum of squared residuals from the previous topic.

The correspondence to the linear algebra is exact:

Graph	Information matrix
variable	diagonal block
factor between $i$ and $j$	off-diagonal block $(i, j)$
no shared factor	structural zero
eliminating a variable	Schur complement on its neighbours

The Schur complement, and why bundle adjustment uses it

$\begin{bmatrix} H_{pp} & H_{pl} \\ H_{pl}^\top & H_{ll} \end{bmatrix} \begin{pmatrix} \Delta_p \\ \Delta_l \end{pmatrix} = -\begin{pmatrix} b_p \\ b_l \end{pmatrix}$

Order the variables poses-first, landmarks-second. H_ll is block-diagonal: no factor connects two landmarks directly.
$\Delta_l = -H_{ll}^{-1}\left(b_l + H_{pl}^\top \Delta_p\right)$

Solve the lower block for the landmarks. Inverting H_ll is cheap precisely because it is block-diagonal — one small inverse per landmark.
$\left(H_{pp} - H_{pl}H_{ll}^{-1}H_{pl}^\top\right)\Delta_p = -b_p + H_{pl}H_{ll}^{-1}b_l$

Substitute back. The reduced camera system involves only the poses, of which there are far fewer than landmarks.
$\text{fill-in: } (i,j) \ne 0 \iff \text{poses } i, j \text{ saw a common landmark}$

The price. The reduced matrix is denser than the original: eliminating a landmark connects every pose that observed it. Ordering the elimination to minimise this is what a good sparse solver spends its time on.

Insight Loop closure is one edge and a global change

A loop closure adds a single factor between two poses that may be thousands of steps apart — one off-diagonal block far from the band. Detecting it is a recognition problem; applying it is what redistributes accumulated drift across the whole trajectory, because the information propagates along every path in the graph between the two poses.

The asymmetry is stark: adding the edge is trivial, and one wrong edge is catastrophic. A false loop closure asserts, with high confidence, that two places are the same place. The optimiser has no way to disbelieve it, and folds the map to comply. This is why loop-closure verification is geometric (RANSAC on the putative match) and not just appearance-based, and why robust kernels or switchable constraints are applied to those factors specifically.

Check yourself

Why do incremental smoothers re-order variables rather than just appending new ones?

Show answer

Because fill-in depends on elimination order, and the best order changes as the graph grows. Appending naively produces a factorisation with steadily worse sparsity, so the cost per update creeps up until it dominates. Incremental systems (iSAM2 and relatives) re-eliminate only the affected subtree and periodically re-order, keeping the factorisation close to what a batch solve with a good ordering would have produced — which is what makes the update cost track the size of the change rather than the size of the map.