Kalman & Particle Filters

Filtering is the time-recursive cousin of posterior inference. The unknown is a hidden state $x_k$ that evolves over time according to some dynamics $x_k = f(x_{k-1}) + w_k$; what you see are noisy observations $y_k = h(x_k) + v_k$. At each step, the goal is the filtering posterior $p(x_k \mid y_{1:k})$ — the belief over the current state given everything observed so far. The four methods below differ in what they assume about $f$, $h$, and the noise, and in how they represent the belief.

1. The state-space model

A discrete-time state-space model is two equations:

where $w_k$ and $v_k$ are process and observation noise. The filtering job is to compute $p(x_k \mid y_{1:k})$ sequentially, updating the belief by one observation at a time. Two recursions do the work:

• Predict: push the belief forward through the dynamics. $p(x_k \mid y_{1:k-1}) = \int p(x_k \mid x_{k-1})\,p(x_{k-1} \mid y_{1:k-1})\,dx_{k-1}$.
• Update: tilt the prediction by the new observation's likelihood. $p(x_k \mid y_{1:k}) \propto p(y_k \mid x_k)\,p(x_k \mid y_{1:k-1})$.

Whether either integral has a closed form depends on the assumptions about $f$, $h$, and the noise. The four methods below sit on a tradeoff ladder: start with an exact Gaussian closed form, then relax linearity, then relax the local-linearization requirement, then finally relax the Gaussian-belief restriction entirely.

2. Closed-form filtering: the Kalman family

closed-form Kalman filter (linear-Gaussian)

If $f$ and $h$ are linear ($x_k = Fx_{k-1} + w_k,\ y_k = Hx_k + v_k$) and the noises are Gaussian, the filtering distribution stays Gaussian forever and is given exactly by:

This is not a Monte Carlo method; it is the closed-form posterior for the linear-Gaussian special case. Use it when you can.

closed-form Extended Kalman filter (EKF)

For mildly nonlinear $f,h$, linearize at the current mean: $F_k = \partial f/\partial x\big|_{\hat x_{k-1}}$, $H_k = \partial h/\partial x\big|_{\hat x_k^-}$, then apply the standard Kalman equations. Cheap and widely deployed, but a poor approximation when the local linearization disagrees with the true function over the spread of the prior.

closed-form Unscented Kalman filter (UKF)

Instead of linearizing the function, propagate a deterministic set of $2n+1$ sigma points through the true nonlinear $f,h$ and refit a Gaussian to their image. Second-order accurate, requires no Jacobians, same cost as EKF. Still fundamentally Gaussian, and fails for multimodal or heavy-tailed posteriors.

Figure 1 compares the filtering approximations on one nonlinear update. Kalman-style methods keep only a Gaussian belief; the difference is how they push that Gaussian through nonlinear dynamics and observations.

3. Sequential Monte Carlo

When the state-space model is genuinely nonlinear or non-Gaussian, no closed form exists and Gaussian approximations break. SMC represents $p(x_{0:k}\mid y_{1:k})$ by a weighted cloud of particles $\{(x^{(i)}_{0:k}, w^{(i)}_k)\}_{i=1}^N$ and updates the cloud as each new observation arrives.

smc Sequential importance sampling (SIS)

Apply importance sampling step by step. With proposal $\pi(x_k\mid x_{0:k-1}, y_{1:k})$, the weights update recursively:

The catastrophe: after a few steps almost all weight ends up on one particle. This is weight degeneracy, and it is the reason SIS by itself is essentially never used.

smc Particle filter / SIR (bootstrap)

Add a resampling step: whenever the effective sample size drops below a threshold, draw $N$ new particles with replacement from the weighted cloud, duplicating heavy particles and killing light ones, and reset all weights to $1/N$. The simplest variant, the bootstrap filter, uses the prior $p(x_k\mid x_{k-1}^{(i)})$ as the proposal, which collapses the weight update to just the likelihood:

Variants improve on the bootstrap proposal: the optimal proposal $\pi(x_k\mid x_{k-1}^{(i)}, y_k)$ minimizes weight variance but is tractable only for special models; local-linearization proposals use an EKF or UKF on each particle to construct a locally near-optimal Gaussian proposal. Resampling itself has variants (multinomial, stratified, systematic, residual) that differ in variance.

Resampling cures weight degeneracy but introduces sample impoverishment: heavy particles get duplicated and the cloud loses diversity. Roughening (jittering particles by a small noise) and MCMC moves between resampling steps are the standard remedies.

Figure 2 runs SIS and a bootstrap particle filter on the same nonlinear tracking problem, so the weight-collapse failure and the resampling fix are visible side by side.

4. Shared filtering structure

All four algorithms share the same predict-then-update recursion. They differ in how the predict pushes the belief forward, how the update incorporates $y_k$, and what kind of belief they carry.

Each column relaxes one assumption from the column to its left. Reading across Predict shows the relaxation explicitly: matrix multiply by a fixed $F$ becomes a Jacobian-at-the-mean, then a Jacobian-free sigma-point propagation, then a non-Gaussian particle propagation. The following cards zoom in on each step.

5. Pair by pair: what changes between methods

Three transitions, each a single design swap. The pseudocode bodies have the same structure; only the highlighted lines change.

x̂_0, P_0 = prior
for k = 1 to K:
    # predict
    x̂⁻ = F · x̂_{k-1}
    P⁻ = F · P_{k-1} · Fᵀ + Q
    # update
    K = P⁻ · Hᵀ · (H · P⁻ · Hᵀ + R)⁻¹
    x̂_k = x̂⁻ + K · (y_k − H · x̂⁻)
    P_k = (I − K · H) · P⁻
return chain (x̂_k, P_k)

x̂_0, P_0 = prior
for k = 1 to K:
    # predict (linearize dynamics)
    F_k = ∂f/∂x |_{x̂_{k-1}}
    x̂⁻ = f(x̂_{k-1})
    P⁻ = F_k · P_{k-1} · F_kᵀ + Q
    # update (linearize observation)
    H_k = ∂h/∂x |_{x̂⁻}
    K = P⁻ · H_kᵀ · (H_k · P⁻ · H_kᵀ + R)⁻¹
    x̂_k = x̂⁻ + K · (y_k − h(x̂⁻))
    P_k = (I − K · H_k) · P⁻
return chain (x̂_k, P_k)

x̂_0, P_0 = prior
for k = 1 to K:
    # predict
    F_k = ∂f/∂x |_{x̂_{k-1}}
    x̂⁻ = f(x̂_{k-1})
    P⁻ = F_k · P_{k-1} · F_kᵀ + Q
    # update
    H_k = ∂h/∂x |_{x̂⁻}
    K = P⁻ · H_kᵀ · (H_k · P⁻ · H_kᵀ + R)⁻¹
    x̂_k = x̂⁻ + K · (y_k − h(x̂⁻))
    P_k = (I − K · H_k) · P⁻
return chain (x̂_k, P_k)

x̂_0, P_0 = prior
for k = 1 to K:
    # predict
    σ_j = sigma_points(x̂_{k-1}, P_{k-1})
    σ'_j = f(σ_j)        # pass through true f
    x̂⁻ = Σ_j w_j · σ'_j
    P⁻ = Σ_j w_j · (σ'_j − x̂⁻)(σ'_j − x̂⁻)ᵀ + Q
    # update
    γ_j = h(σ'_j)        # pass through true h
    C = Σ_j w_j · (σ'_j − x̂⁻)(γ_j − γ̄)ᵀ
    S = Σ_j w_j · (γ_j − γ̄)(γ_j − γ̄)ᵀ + R
    K = C · S⁻¹
    x̂_k = x̂⁻ + K · (y_k − γ̄)
    P_k = P⁻ − K · S · Kᵀ
return chain (x̂_k, P_k)

x̂_0, P_0 = prior Gaussian
for k = 1 to K:
    # predict
    σ_j = sigma_points(x̂_{k-1}, P_{k-1})
    σ'_j = f(σ_j)
    x̂⁻, P⁻ = mean & cov of σ'_j;  P⁻ += Q
    # update
    γ_j = h(σ'_j)
    K = cov(σ'_j, γ_j) · (cov(γ_j) + R)⁻¹
    x̂_k = x̂⁻ + K · (y_k − mean(γ_j))
    P_k = P⁻ − K · cov(γ_j, σ'_j)

return chain (x̂_k, P_k)

{x^(i)_0}_{i=1..N}, w^(i) = 1/N    # cloud, not Gaussian
for k = 1 to K:
    # predict
    for each i:
        x^(i)_k ~ p(x_k | x^(i)_{k-1})
                                  # sample from dynamics
    # update
    for each i:
        w^(i) ∝ w^(i)_{k-1} · p(y_k | x^(i)_k)
    normalize w^(i)
    if ESS(w) < τ:
        resample N particles ∝ w
        w^(i) ← 1/N
return chain of clouds {x^(i)_k, w^(i)_k}

6. Filter choice by model

The decision is mostly about how nonlinear the dynamics are and whether the posterior stays unimodal. Tags echo the section colors: closed-form means a Gaussian closed-form posterior (no sampling), smc means weighted particles updated sequentially.