Thrun et al., Chapter 12

The Sparse Extended Information Filter

SEIF SLAM: constant-time online SLAM via sparsification, active features, and amortized map recovery.

Prerequisites: Chapters 10-11 (EKF SLAM, EIF SLAM, information form).

Chapters

Simulations

Quizzes

Chapter 0: Best of Both Worlds

EKF SLAM is online but O(N²). EIF SLAM is efficient but batch. Can we get an online algorithm that's also efficient? The Sparse Extended Information Filter (SEIF) achieves exactly this.

The SEIF insight: The online SLAM information matrix is approximately sparse. Strong links exist only between nearby features and between the robot and recently observed features. Distant features have near-zero links. SEIF enforces exact sparsity by setting near-zero links to zero (sparsification), enabling constant-time updates independent of map size.

The SEIF maintains the same state as EKF SLAM — current pose x_t and map m — but in information form (Ω_t, ξ_t). Four steps per update: measurement, motion, sparsification, and state estimation.

Check: What does SEIF achieve that neither EKF SLAM nor EIF SLAM can?

Online SLAM with update time independent of map size (constant time) Perfect maps with no approximation SLAM without sensor data

Chapter 1: Active Features

SEIF divides landmarks into two categories:

Type	Definition	Link to Robot
Active	Recently observed landmarks	Non-zero Ω_{x,m_j}
Passive	Not recently observed	Zero Ω_{x,m_j}

The number of active features is bounded by a constant (typically 5-20). Only active features participate in the expensive parts of the update. Passive features sit quietly in the information matrix, their inter-feature links preserved but no direct link to the current robot pose.

Why bounding active features matters: The motion update's complexity depends on the number of active features. With k active features, the motion update touches a (3+2k) × (3+2k) submatrix. If k is bounded by a constant, the update is O(1). This is the key to constant-time SLAM.

Check: What determines whether a feature is active in SEIF?

Whether it has a non-zero link to the current robot pose in the information matrix Whether it has been observed at least once Whether it is within 10 meters of the robot

Chapter 2: Measurement Update

The measurement update is the easiest part. Observing landmark j adds a local constraint to Ω and ξ:

Ω_t = Ω̄_t + Σ_i H_t^iT Q_t^-1 H_tⁱ
ξ_t = ξ̄_t + Σ_i H_t^iT Q_t^-1 (z_tⁱ - ẑ_tⁱ + H_tⁱ μ_t)

Each measurement only modifies the block linking x_t and m_j — a 5×5 addition. This is constant time per observation, regardless of map size.

Contrast with EKF: In EKF SLAM, a measurement update requires modifying the entire (3+3N) × (3+3N) covariance matrix — O(N²). In SEIF, it's a local addition to Ω — O(1). This is the fundamental efficiency advantage of the information form for measurements.

After the measurement update, the observed landmark becomes active (if it wasn't already). If there are now too many active features, sparsification will deactivate one.

Check: Why is the SEIF measurement update O(1)?

It only modifies the local block linking the robot pose and the observed landmark in the information matrix It ignores most landmarks It uses approximation

Chapter 3: Motion Update

The motion update is trickier. When the robot moves, it loses information about its pose relative to all active features. This manifests as:

• Links between robot and active features weaken (motion noise degrades pose certainty).

• Links between pairs of active features strengthen (the relative positions of features are unaffected by robot motion).

Information shifting: Robot motion shifts information from robot-feature links into feature-feature links. Before motion, the robot "mediates" the connection between features. After motion, the robot's pose is less certain, but the features' relative positions are preserved. This information redistribution is a key structural property of SEIF.

The motion update only involves active features — a bounded-size submatrix. If k features are active, the computation is O(k²), which is O(1) for bounded k.

The side effect: motion introduces new feature-feature links between all pairs of active features. This is how the information matrix accumulates structure over time.

Check: What happens to information during the SEIF motion update?

Information shifts from robot-feature links (which weaken) to feature-feature links (which strengthen) Information is lost entirely Only the robot pose is updated

Chapter 4: Sparsification

Sparsification is SEIF's defining approximation. It deactivates features by removing their link to the robot pose:

1. Choose an active feature m_j to deactivate (e.g., the one with the weakest robot link).

2. Set Ω_{x,m_j} = 0 (remove the link).

3. Redistribute the removed information into links between remaining active features and the robot.

The approximation: Setting a link to zero loses information. This is an irreversible approximation. However, the lost information was weak (the feature hasn't been seen recently), so the impact is small. The benefit is enormous: the number of active features stays bounded, guaranteeing constant-time updates forever.

Sparsification can be performed in O(k²) time, where k is the number of active features. Since k is bounded by a constant, this is O(1).

Check: What does SEIF sparsification sacrifice to achieve constant-time updates?

It loses a small amount of information by setting weak robot-feature links to zero It discards old landmarks It ignores new measurements

Chapter 5: Map Recovery

The information form stores Ω and ξ, but for data association and visualization we need the means μ = Ω^-1ξ. Inverting the full information matrix would cost O(N³) — defeating the purpose.

SEIF uses amortized approximate map recovery: an iterative relaxation algorithm that propagates mean estimates through the information graph, one node at a time:

μ_j ← Ω_j,j^-1 (ξ_j - Σ_k≠j Ω_j,k μ_k)

Local updates, global convergence: Each node update is O(1) (it only looks at its neighbors in the information graph, which are sparse). A fixed number of updates per time step keeps the computation bounded. The estimates converge to the true means over time, though with some lag. This "lazy" recovery is what makes SEIF truly constant-time.

Check: How does SEIF recover mean estimates without inverting the full information matrix?

Iterative relaxation: propagate estimates through the sparse graph, updating a fixed number of nodes per step It uses the EKF covariance instead It doesn't recover means — it only stores information

Chapter 6: How Sparse?

How many active features should SEIF maintain? This is a key design parameter.

Active Features	Update Cost	Approximation Error	Practical Range
Very few (2-3)	Very fast	High (too much information lost)	Not recommended
Moderate (5-10)	Fast	Low	Typical choice
Many (20+)	Moderate	Very low	When accuracy is critical

The empirical finding: For most indoor environments, 5-10 active features provide an excellent balance. The information lost through sparsification is small because features that haven't been observed recently contribute little to the current pose estimate. The quality of the resulting map is comparable to EKF SLAM.

Check: Why is it acceptable to deactivate features in SEIF?

Features not recently observed contribute little to the current pose estimate, so the information loss is small Deactivated features are deleted It only works in simple environments

Chapter 7: Data Association

Data association in SEIF requires mean estimates (for predicting expected measurements) and covariance estimates (for Mahalanobis distances). Both come from the amortized map recovery.

Two approaches are used: incremental data association using the approximate means and covariances from the relaxation algorithm, and tree-based search for more complex scenarios where multiple features are observed simultaneously and mutual exclusion must be enforced.

Tree-based search: When the robot observes multiple features at once, the correspondences are not independent (mutual exclusion: two observations can't match the same landmark). Tree search explores the space of joint assignments, pruning branches with low likelihood. This is more expensive but much more robust than independent ML correspondence.

Check: Why does SEIF need approximate means for data association?

To predict expected measurements and compute Mahalanobis distances for matching observations to landmarks To display the map To control the robot

Chapter 8: Multi-Robot SLAM

SEIF naturally extends to multi-robot SLAM. When two robots meet and establish correspondence between their feature maps, the information can be fused by adding the information matrices:

Ω_fused = Ω_A + Ω_B - Ω_prior

Why information form is natural for multi-robot fusion: Combining independent evidence is additive in information form. Two robots that explored different areas have independent information. Adding their information matrices is the correct Bayesian fusion — no complicated covariance manipulation needed.

The challenge: establishing correspondence between the two robots' feature maps. If robot A calls a landmark "feature 3" and robot B calls the same landmark "feature 7," we need to discover this equivalence. Meeting in the same place (mutual observation) or observing shared landmarks enables this discovery.

Check: Why is the information form natural for multi-robot SLAM fusion?

Combining independent information is additive in information form — just add the information matrices Robots can share sensors The information form uses less bandwidth

Chapter 9: Summary

Algorithm	Online?	Per-step Cost	Map Size	Representation
EKF SLAM	Yes	O(N²)	~1,000	Dense covariance
EIF SLAM	No (batch)	O(1) add, O(T³) solve	~100,000	Sparse information
SEIF SLAM	Yes	O(1)	~100,000	Sparse information (approx.)

What comes next: SEIF handles the continuous SLAM problem efficiently. But what about data association in complex environments? Chapter 13 introduces EM-based mapping for handling unknown data association, and Chapter 14 presents fast incremental mapping via gradient descent.

"The trick is not to track everything —
it's to know which things to stop tracking
without losing what matters."

Check: What is the key approximation that enables SEIF's constant-time updates?

Sparsification — setting weak robot-feature links to zero and redistributing information Ignoring motion noise Using a fixed number of particles