The Kalman filter as recursive Bayesian estimation
The Kalman filter tracks a quantity observed through a noisy sensor by alternating prediction and update, with a gain that determines the weight given to each measurement. A simulation shows the effect of sensor outages and mis-specified noise.
A satellite navigation receiver may report a position that is clearly wrong, for example in a river next to a bridge. Combining a model of the motion with the noisy measurement, and weighting each by its reliability, gives a better estimate.
The Kalman filter formalises this combination. It was used for Apollo navigation, it runs in mobile location services, and it is Bayes' rule applied recursively, one measurement at a time.
Rudolf Kálmán published the filter in 1960 as a recursive solution to the linear filtering problem that Wiener and Kolmogorov had solved for stationary signals in the 1940s. Within a few years it was in operational use: McGee and Schmidt describe how the NASA Ames group turned it into a navigation tool for Apollo. Its statistical interpretation came later. Meinhold and Singpurwalla's short 1983 paper, "Understanding the Kalman filter", showed that each step is a Bayesian update of a normal prior with a normal likelihood. Harvey (1989) and Durbin and Koopman (2012) then made state-space models and the Kalman filter the standard machinery of time-series econometrics, which is why the same algorithm estimates both a satellite's orbit and the trend in unemployment.
The model
Take the simplest case: a quantity that wanders at random, and a sensor that reports it with noise.
The first equation is the state (how the world moves), the second the observation (what is observed). The objective is the best estimate of given , and a correct statement of its uncertainty.
Prediction and update
Suppose that after time the belief about the state is normal with mean and variance . Two steps follow.
Predict. The state wanders, so the uncertainty grows: the mean stays at and the variance becomes .
Update. A measurement arrives. Combining a normal prior with a normal likelihood gives a normal posterior whose mean is a weighted average,
The Kalman gain is the share of the surprise that is accepted. If the sensor is noisy ( large), is small and the prediction is largely retained. If the prediction is uncertain ( large), is close to 1 and the measurement dominates. The variances set the gain, so nothing needs tuning by hand.
Steady-state gain
Repeat predict and correct and the variance converges to a fixed point, so the gain does too. Solving with gives
With and the gain settles at about 0.13: each new measurement moves the estimate by an eighth of its surprise. In steady state the Kalman filter is an exponentially weighted moving average, with the weight determined by the model rather than chosen arbitrarily.
Missing measurements
If a measurement is missing, there is nothing to correct with. The filter only predicts: the mean stays where it was and the variance grows by at every step. The uncertainty band widens linearly until data return, and then collapses again. Many ad hoc smoothers do not represent this increase in uncertainty.
A car navigation application in a tunnel behaves in exactly this way. The satellite signal is lost, the application keeps moving the car along the road at its last known speed, and the position becomes steadily less certain. When the car leaves the tunnel and the signal returns, the first measurements receive a large weight and the position is corrected within seconds.
Mis-specified noise
The filter is optimal only if and are right. If the assumed state noise is too small, the filter responds too slowly: it lags behind real changes and its band is too narrow. If it is too large, the filter follows each noisy measurement too closely. Both errors are common and easy to detect. A navigation application that trusts its motion model too much keeps showing the car on the motorway for some time after it has taken an exit; one that trusts the measurements too much makes the car jump between parallel streets in a city centre, where reflections from buildings disturb the signal.
The figure below shows a random walk, a noisy sensor and a filter whose noise assumptions can be changed.
Suggested settings:
- Convergence of the gain. Press "New data". The gain starts near 1 (no prior knowledge, so the measurement dominates) and drops within a few steps to the theoretical 0.13 shown in the readout. The filter's error is about a third of the sensor's.
- Sensor outage. Turn on the outage. Between steps 80 and 110 the band widens steadily and the estimate goes flat: the filter only predicts, with increasing uncertainty. When data return, the gain rises and the band narrows quickly.
- Underestimated state noise. Set the filter's belief about to ×0.01. The estimate lags behind the true path, and the coverage readout drops well below 95%: the filter is overconfident.
- Overestimated state noise. Set it to ×100. The estimate follows the measurements almost exactly, and its error rises towards the sensor's own.
- Noisier sensor. Raise to 10. The gain falls, the estimate becomes smoother, and the steady-state formula predicts the new gain before the filter reaches it.
Derivation of the update. With prior and likelihood , the log-posterior is, up to a constant,
It is quadratic in , so the posterior is normal. Its precision is the sum of the precisions, , which rearranges to with . Its mean is the precision-weighted average . This is the complete filter: Bayes' rule for normals, applied once per time step.
The same two lines, with matrices instead of numbers, track position and velocity together, fuse a GPS with an accelerometer, or estimate an unobserved trend in economic data. They also connect to two other ideas on this site: the AR(1) model is a state-space model with an observed state, and the Wiener filter solves the same problem in the frequency domain, for stationary signals. The advantage of the Kalman filter is that it operates recursively, in real time, and reports its uncertainty at every step. When the hidden state takes a few discrete values instead of a continuous one, the same predict-and-update logic becomes Hamilton's filter for recessions as a hidden state.
References
- R. E. Kalman, "A new approach to linear filtering and prediction problems", Journal of Basic Engineering, 82(1), 35-45, 1960.
- L. A. McGee and S. F. Schmidt, Discovery of the Kalman Filter as a Practical Tool for Aerospace and Industry, NASA Technical Memorandum 86847, 1985.
- R. J. Meinhold and N. D. Singpurwalla, "Understanding the Kalman filter", The American Statistician, 37(2), 123-127, 1983.
- A. C. Harvey, Forecasting, Structural Time Series Models and the Kalman Filter, Cambridge University Press, 1989.
- J. Durbin and S. J. Koopman, Time Series Analysis by State Space Methods, 2nd ed., Oxford University Press, 2012.