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
Predict. By induction . A linear map of a Gaussian plus independent Gaussian noise is Gaussian, with means mapped and covariances added:
Joint. The new measurement is another linear function plus independent noise, so state and measurement are jointly Gaussian given the past:
Condition on with the Gaussian conditioning formula (the same Schur complement as in Gaussian Processes & Bayesian ML):
Byproduct. Under the model the innovations are independent, , so the likelihood of all measurements comes for free. It is used to fit and , and should look like a variable if the model is right. ∎
Two rewritings of the Kalman filter matter in practice. The information form propagates and makes the update additive, : precisions add, as in one dimension. The Joseph form is valid for any gain and keeps 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 . If is detectable and is stabilizable, it converges from any to the unique stabilizing solution of the discrete algebraic Riccati equation, and the gain converges to a constant (Anderson & Moore, 1979).
For , with variances and , the predicted variance and the filtered variance satisfy, at the fixed point,
Take the positive root. For it is the golden ratio times :
The gain is then , since , and the filtered variance is :
In steady state the filter is exponential smoothing, . That heuristic is the optimal filter for a random walk seen through noise, with its smoothing constant set by the ratio .
Same random walk, but now the process noise is four times the sensor noise, . What is the steady-state Kalman gain?
Show the answer
0.83
, so . A state that wanders fast makes old estimates stale, so the filter trusts each new measurement more. As the gain goes to 0 and the filter averages over a long window.
Nonlinear models: extended and unscented filters
For and , the belief stops being Gaussian. Two classical fixes keep a Gaussian anyway:
- The extended Kalman filter (EKF) linearizes, using the Jacobians at and at in the covariance equations, while propagating the means through and themselves.
- The unscented Kalman filter (UKF; Julier & Uhlmann, 1997) pushes deterministically chosen sigma points, and the columns of a matrix square root of , 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, , 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 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 , 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
Target the path posterior. Its recursion multiplies the previous posterior by one transition and one likelihood:
Extend each particle with a proposal and update its importance weight by the ratio of target to proposal:
The bootstrap particle filter (Gordon, Salmond & Smith, 1993) proposes from the transition, so the weight is the likelihood. The proposal , which looks at the new measurement, minimizes the variance of the incremental weight; its weight is the predictive likelihood:
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 :
Key takeaways
- The Kalman filter is Gaussian conditioning, step by step: predict , then update with . The innovations are independent, which gives the likelihood for fitting and .
- 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 the steady-state gain is , 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 , 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.
The process and sensor noises of a linear system are uniform, not Gaussian, with known covariances. What remains true of the Kalman filter?
- Nothing: it is derived from Gaussian conditioning
- It still computes the exact posterior mean
- It is the best estimator that is an affine function of the measurements, with error covariance
- It is unbiased but its covariance is meaningless
Show the answer
C. It is the best estimator that is an affine function of the measurements, with error covariance
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.
A random walk with process-noise variance is observed with sensor-noise variance . What is the steady-state Kalman gain?
Show the answer
B.
The fixed point is , so . The gain exceeds because the prediction carries both the old estimate's uncertainty and the new process noise.
After an update, four particles have normalized weights . What is their effective sample size?
- 4
- 2
- About 2.9
- 1
Show the answer
C. About 2.9
, so . With a resampling threshold of , this set would not yet be resampled.
A bootstrap particle filter tracks a system whose observations have independent components. To keep the weights from collapsing onto a single particle, how must the number of particles grow with ?
- It need not grow
- Linearly in
- Like
- Exponentially in
Show the answer
D. Exponentially in
The log-weights are sums of independent log-likelihood terms, so their variance grows linearly with , and avoiding collapse requires 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).