Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Kalman & Particle Filters

Tracking hidden state with noisy sensors.

Rudolf Kálmán published his recursive estimator in 1960, and within a decade it was helping navigate Apollo spacecraft. Its derivation is a few lines of Gaussian algebra, its optimality has two distinct meanings, and its failure on nonlinear, multimodal problems motivated the particle filter, which trades equations for samples and then runs into the curse of dimensionality. This lesson works through both filters, with the theorems that say when each can be trusted.

What you’ll learn

  • Derive the Kalman filter by Gaussian conditioning, and prove both of its optimality properties: exact posterior for linear-Gaussian models, best linear estimator otherwise.
  • Analyze the steady state through the Riccati equation, including the golden-ratio gain of the scalar random walk.
  • Explain how the extended and unscented Kalman filters handle nonlinearity, and how they fail.
  • Derive sequential importance resampling, quantify weight degeneracy, and state the convergence results and the curse of dimensionality for particle filters.

The Kalman filter from Gaussian conditioning

DerivationProof
  1. xt∣z1:t−1∼N(Fμt−1, FΣt−1F⊤+Q)\mathbf x_t\mid\mathbf z_{1:t-1}\sim\mathcal N\big(F\boldsymbol\mu_{t-1},\ F\Sigma_{t-1}F^\top+Q\big)

    Predict. By induction xt−1∣z1:t−1∼N(μt−1,Σt−1)\mathbf x_{t-1}\mid\mathbf z_{1:t-1}\sim\mathcal N(\boldsymbol\mu_{t-1},\Sigma_{t-1}). A linear map of a Gaussian plus independent Gaussian noise is Gaussian, with means mapped and covariances added:

  2. (xtzt)∣ z1:t−1∼N((μt−Hμt−),(Σt−Σt−H⊤HΣt−St))\begin{pmatrix}\mathbf x_t\\ \mathbf z_t\end{pmatrix}\Big|\ \mathbf z_{1:t-1}\sim\mathcal N\left(\begin{pmatrix}\boldsymbol\mu_t^-\\ H\boldsymbol\mu_t^-\end{pmatrix},\begin{pmatrix}\Sigma_t^-&\Sigma_t^-H^\top\\ H\Sigma_t^-&S_t\end{pmatrix}\right)

    Joint. The new measurement is another linear function plus independent noise, so state and measurement are jointly Gaussian given the past:

  3. μt=μt−+Σt−H⊤St−1(zt−Hμt−),Σt=Σt−−Σt−H⊤St−1HΣt−=(I−KtH) Σt−\boldsymbol\mu_t=\boldsymbol\mu_t^-+\Sigma_t^-H^\top S_t^{-1}\big(\mathbf z_t-H\boldsymbol\mu_t^-\big),\qquad\Sigma_t=\Sigma_t^--\Sigma_t^-H^\top S_t^{-1}H\Sigma_t^-=(I-K_tH)\,\Sigma_t^-

    Condition on zt\mathbf z_t with the Gaussian conditioning formula (the same Schur complement as in Gaussian Processes & Bayesian ML):

  4. log⁡p(z1:T)=−12∑t=1T(νt⊤St−1νt+log⁡det⁡(2πSt))\log p(\mathbf z_{1:T})=-\frac12\sum_{t=1}^T\Big(\boldsymbol\nu_t^\top S_t^{-1}\boldsymbol\nu_t+\log\det(2\pi S_t)\Big)

    Byproduct. Under the model the innovations are independent, νt∼N(0,St)\boldsymbol\nu_t\sim\mathcal N(\mathbf 0,S_t), so the likelihood of all measurements comes for free. It is used to fit QQ and RR, and νt⊤St−1νt\boldsymbol\nu_t^\top S_t^{-1}\boldsymbol\nu_t should look like a χ2\chi^2 variable if the model is right. ∎

Two rewritings of the Kalman filter matter in practice. The information form propagates Σ−1\Sigma^{-1} and makes the update additive, Σt−1=(Σt−)−1+H⊤R−1H\Sigma_t^{-1}=(\Sigma_t^-)^{-1}+H^\top R^{-1}H: precisions add, as in one dimension. The Joseph form Σt=(I−KtH)Σt−(I−KtH)⊤+KtRKt⊤\Sigma_t=(I-K_tH)\Sigma_t^-(I-K_tH)^\top+K_tRK_t^\top is valid for any gain and keeps Σt\Sigma_t symmetric positive semidefinite under rounding, which the short form does not guarantee.

Two kinds of optimality, and the steady state

The covariance recursion does not depend on the data, so it can be run offline. It is the Riccati recursion Σt+1−=F(Σt−−Σt−H⊤(HΣt−H⊤+R)−1HΣt−)F⊤+Q\Sigma_{t+1}^-=F\big(\Sigma_t^--\Sigma_t^-H^\top(H\Sigma_t^-H^\top+R)^{-1}H\Sigma_t^-\big)F^\top+Q. If (F,H)(F,H) is detectable and (F,Q1/2)(F,Q^{1/2}) is stabilizable, it converges from any Σ0⪰0\Sigma_0\succeq0 to the unique stabilizing solution of the discrete algebraic Riccati equation, and the gain converges to a constant (Anderson & Moore, 1979).

DerivationThe scalar random walk: a golden-ratio gain
  1. p−=p+q,p=p−rp−+r⟹(p−)2−q p−−q r=0p^-=p+q,\qquad p=\frac{p^-r}{p^-+r}\quad\Longrightarrow\quad(p^-)^2-q\,p^--q\,r=0

    For xt=xt−1+wtx_t=x_{t-1}+w_t, zt=xt+vtz_t=x_t+v_t with variances qq and rr, the predicted variance p−p^- and the filtered variance pp satisfy, at the fixed point,

  2. p−=q+q2+4qr2=φ r(q=r)p^-=\frac{q+\sqrt{q^2+4qr}}2=\varphi\,r\quad(q=r)

    Take the positive root. For q=rq=r it is the golden ratio φ=(1+5)/2\varphi=(1+\sqrt5)/2 times rr:

  3. K=p−p−+r=φφ+1=1φ≈0.618K=\frac{p^-}{p^-+r}=\frac{\varphi}{\varphi+1}=\frac1\varphi\approx0.618

    The gain is then 1/φ1/\varphi, since φ+1=φ2\varphi+1=\varphi^2, and the filtered variance is r/φ≈0.618 rr/\varphi\approx0.618\,r:

  4. x^t=(1−K) x^t−1+K zt\hat x_t=(1-K)\,\hat x_{t-1}+K\,z_t

    In steady state the filter is exponential smoothing, x^t=x^t−1+K(zt−x^t−1)\hat x_t=\hat x_{t-1}+K(z_t-\hat x_{t-1}). That heuristic is the optimal filter for a random walk seen through noise, with its smoothing constant set by the ratio q/rq/r.

Predict before you look

Same random walk, but now the process noise is four times the sensor noise, q=4rq=4r. What is the steady-state Kalman gain?

Show the answer

0.83

p−=(4r+16r2+16r2)/2=(2+22) r≈4.83 rp^-=\big(4r+\sqrt{16r^2+16r^2}\big)/2=(2+2\sqrt2)\,r\approx4.83\,r, so K=4.83/5.83≈0.83K=4.83/5.83\approx0.83. A state that wanders fast makes old estimates stale, so the filter trusts each new measurement more. As q/r→0q/r\to0 the gain goes to 0 and the filter averages over a long window.

Nonlinear models: extended and unscented filters

For xt=f(xt−1)+wt\mathbf x_t=f(\mathbf x_{t-1})+\mathbf w_t and zt=h(xt)+vt\mathbf z_t=h(\mathbf x_t)+\mathbf v_t, the belief stops being Gaussian. Two classical fixes keep a Gaussian anyway:

  • The extended Kalman filter (EKF) linearizes, using the Jacobians Ft=∂f/∂xF_t=\partial f/\partial\mathbf x at μt−1\boldsymbol\mu_{t-1} and Ht=∂h/∂xH_t=\partial h/\partial\mathbf x at μt−\boldsymbol\mu_t^- in the covariance equations, while propagating the means through ff and hh themselves.
  • The unscented Kalman filter (UKF; Julier & Uhlmann, 1997) pushes 2n+12n+1 deterministically chosen sigma points, μ\boldsymbol\mu and μ±\boldsymbol\mu\pm the columns of a matrix square root of (n+κ)Σ(n+\kappa)\Sigma, through the nonlinearity and refits a mean and covariance. It needs no derivatives and captures the transformed mean and covariance more accurately than linearization.
Think first A robot measures only the bearing to a landmark, h(x)=atan2⁡(yL−y, xL−x)h(\mathbf x)=\operatorname{atan2}(y_L-y,\ x_L-x), and its position prior is wide. Why can an EKF become overconfident and diverge?

The Jacobian is evaluated at the current mean, but over a wide prior the bearing function curves strongly, so the linearization misrepresents how the measurement depends on the state. The update then shrinks Σ\Sigma as if the measurement were more informative than it is, the filter discounts later measurements that contradict its mean, and the error grows while the reported covariance stays small. Remedies include iterated updates, the UKF, inflating QQ, or a particle filter, which can also represent the banana-shaped or multimodal posteriors that bearing-only problems produce.

Particle filters: resampling, degeneracy and dimension

DerivationSequential importance resampling
  1. p(x0:t∣z1:t) ∝ p(x0:t−1∣z1:t−1) p(xt∣xt−1) p(zt∣xt)p(\mathbf x_{0:t}\mid\mathbf z_{1:t})\ \propto\ p(\mathbf x_{0:t-1}\mid\mathbf z_{1:t-1})\,p(\mathbf x_t\mid\mathbf x_{t-1})\,p(\mathbf z_t\mid\mathbf x_t)

    Target the path posterior. Its recursion multiplies the previous posterior by one transition and one likelihood:

  2. wt(i) ∝ wt−1(i) p(zt∣xt(i)) p(xt(i)∣xt−1(i))q(xt(i)∣xt−1(i),zt)w_t^{(i)}\ \propto\ w_{t-1}^{(i)}\ \frac{p\big(\mathbf z_t\mid\mathbf x_t^{(i)}\big)\,p\big(\mathbf x_t^{(i)}\mid\mathbf x_{t-1}^{(i)}\big)}{q\big(\mathbf x_t^{(i)}\mid\mathbf x_{t-1}^{(i)},\mathbf z_t\big)}

    Extend each particle with a proposal q(xt∣xt−1,zt)q(\mathbf x_t\mid\mathbf x_{t-1},\mathbf z_t) and update its importance weight by the ratio of target to proposal:

  3. q=p(xt∣xt−1): wt∝wt−1 p(zt∣xt);q=p(xt∣xt−1,zt): wt∝wt−1 p(zt∣xt−1)q=p(\mathbf x_t\mid\mathbf x_{t-1}):\ w_t\propto w_{t-1}\,p(\mathbf z_t\mid\mathbf x_t);\qquad q=p(\mathbf x_t\mid\mathbf x_{t-1},\mathbf z_t):\ w_t\propto w_{t-1}\,p(\mathbf z_t\mid\mathbf x_{t-1})

    The bootstrap particle filter (Gordon, Salmond & Smith, 1993) proposes from the transition, so the weight is the likelihood. The proposal p(xt∣xt−1,zt)p(\mathbf x_t\mid\mathbf x_{t-1},\mathbf z_t), which looks at the new measurement, minimizes the variance of the incremental weight; its weight is the predictive likelihood:

  4. ESSt=1∑i(wˉt(i))2,wˉt(i)=wt(i)∑jwt(j)\mathrm{ESS}_t=\frac1{\sum_i\big(\bar w_t^{(i)}\big)^2},\qquad\bar w_t^{(i)}=\frac{w_t^{(i)}}{\sum_jw_t^{(j)}}

    Without resampling, the variance of the weights grows over time (Kong, Liu & Wong, 1994) and the effective sample size collapses. Resample, multinomially or with lower-variance systematic schemes, whenever it falls below a threshold such as N/2N/2:

Key takeaways

  • The Kalman filter is Gaussian conditioning, step by step: predict Σ−=FΣF⊤+Q\Sigma^-=F\Sigma F^\top+Q, then update with K=Σ−H⊤S−1K=\Sigma^-H^\top S^{-1}. The innovations are independent, which gives the likelihood for fitting QQ and RR.
  • It is the exact posterior mean for linear-Gaussian models and the best linear estimator for any noise with the same covariances. The covariance follows a data-independent Riccati recursion; for a random walk with q=rq=r the steady-state gain is 1/φ≈0.6181/\varphi\approx0.618, which turns the filter into exponential smoothing.
  • EKF and UKF keep a single Gaussian through nonlinearities, by linearization or sigma points, and can become overconfident or miss multimodal posteriors.
  • Particle filters reweight samples by the likelihood and resample when the effective sample size drops. Their error is O(1/N)\order{1/\sqrt N}, uniformly in time for mixing models, but the number of particles must grow exponentially with the observation dimension.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

The process and sensor noises of a linear system are uniform, not Gaussian, with known covariances. What remains true of the Kalman filter?

  1. Nothing: it is derived from Gaussian conditioning
  2. It still computes the exact posterior mean E[xt∣z1:t]\E[\mathbf x_t\mid\mathbf z_{1:t}]
  3. It is the best estimator that is an affine function of the measurements, with error covariance Σt\Sigma_t
  4. It is unbiased but its covariance Σt\Sigma_t is meaningless
Show the answer

C. It is the best estimator that is an affine function of the measurements, with error covariance Σt\Sigma_t

The innovations argument uses only means and covariances, so the recursion is the linear minimum-mean-square-error estimator. A nonlinear estimator can beat it, because the posterior mean is no longer affine in the data.

Question 2

A random walk with process-noise variance qq is observed with sensor-noise variance r=qr=q. What is the steady-state Kalman gain?

  1. 0.50.5
  2. 1/φ≈0.6181/\varphi\approx0.618
  3. 11
  4. 1/φ2≈0.3821/\varphi^2\approx0.382
Show the answer

B. 1/φ≈0.6181/\varphi\approx0.618

The fixed point is p−=φrp^-=\varphi r, so K=φ/(φ+1)=1/φK=\varphi/(\varphi+1)=1/\varphi. The gain exceeds 12\tfrac12 because the prediction carries both the old estimate's uncertainty and the new process noise.

Question 3

After an update, four particles have normalized weights 0.5, 0.25, 0.125, 0.1250.5,\ 0.25,\ 0.125,\ 0.125. What is their effective sample size?

  1. 4
  2. 2
  3. About 2.9
  4. 1
Show the answer

C. About 2.9

∑iwˉi2=0.25+0.0625+0.015625+0.015625=0.34375\sum_i\bar w_i^2=0.25+0.0625+0.015625+0.015625=0.34375, so ESS=1/0.34375≈2.9\mathrm{ESS}=1/0.34375\approx2.9. With a resampling threshold of N/2=2N/2=2, this set would not yet be resampled.

Question 4

A bootstrap particle filter tracks a system whose observations have dd independent components. To keep the weights from collapsing onto a single particle, how must the number of particles grow with dd?

  1. It need not grow
  2. Linearly in dd
  3. Like d\sqrt d
  4. Exponentially in dd
Show the answer

D. Exponentially in dd

The log-weights are sums of dd independent log-likelihood terms, so their variance grows linearly with dd, and avoiding collapse requires log⁡N\log N to grow at the same rate. This is the obstacle that pushed weather forecasting toward ensemble Kalman filters.

Further reading

  • R. E. Kalman, "A new approach to linear filtering and prediction problems," Journal of Basic Engineering 82(1), 35–45 (1960).
  • B. D. O. Anderson & J. B. Moore, Optimal Filtering (Prentice-Hall, 1979).
  • N. J. Gordon, D. J. Salmond & A. F. M. Smith, "Novel approach to nonlinear/non-Gaussian Bayesian state estimation," IEE Proceedings F 140(2), 107–113 (1993).
  • A. Doucet & A. M. Johansen, "A tutorial on particle filtering and smoothing: Fifteen years later," in The Oxford Handbook of Nonlinear Filtering (Oxford University Press, 2011).
  • T. Bengtsson, P. Bickel & B. Li, "Curse-of-dimensionality revisited: Collapse of the particle filter in very large scale systems," in Probability and Statistics: Essays in Honor of David A. Freedman (Institute of Mathematical Statistics, 2008).