Tracking with the Kalman filter

A Kalman filter estimates the hidden state of a system that changes over time (here: the position and velocity of a moving object) from noisy measurements. It keeps a Gaussian belief about the state: a mean $\hat x$ (the best guess) and a covariance $P$ (how unsure it is). Two steps repeat for every new measurement:

Predict: move the belief forward with a model of the motion. The guess moves and the uncertainty grows.
Update: compare the prediction with the measurement and correct it. The uncertainty shrinks.

In the first simulation you track a target with a position sensor and see both steps, the Kalman gain and the errors live. In the second one the sensor measures distance and angle, so the problem becomes nonlinear, and you compare the extended Kalman filter with a particle filter. At the end we connect all of this to data assimilation, the method that starts every weather forecast.

1. The tracking simulation #

Press Play and watch the two steps. The black dot (white in dark mode) is the true target, the orange dots are the noisy measurements $z$ . Violet, dashed: the prediction $\hat x^-$ and its 95% ellipse. Blue: the estimate $\hat x$ after the update and its 95% ellipse. The orange dashed arrow is the innovation $\nu = z - H\hat x^-$ (how much the measurement surprised the filter); the blue arrow is the correction $K\nu$ . Pick slow, or press Next, to see predict and update one at a time. The charts show the last 10 seconds.

2. Try this #

Trust the model or trust the sensor? With the circle target, set the process noise $q$ to its smallest value, then to its largest. Question: which setting gives a smooth track that falls behind the target in the turn, and which one gives a track that jumps with every measurement? What to see: with small $q$ the gain $K_{11}$ drops to about $0.12$ and the blue track cuts inside the circle (its RMSE becomes larger than the sensor's). With large $q$ the gain rises to about $0.7$ and the track copies the noise. Near $q = 1$ the filter error is about half the sensor error.
The gain does not look at the data. Press Next a few times. Question: after the predict step, before the measurement is used, is the gain $K$ already known? What to see: yes. $K$ depends only on $P^-$ and $R$ , not on the value of $z$ . After a few seconds it stops changing: the filter reaches a steady state.
Losing the signal. Set Measurements to no-signal zone. Question: inside the grey band, what happens to the ellipse, and what does the gain do at the first measurement after the band? What to see: with no updates the ellipse only grows, and the prediction flies straight on while the target turns. At the first new measurement $K_{11}$ jumps close to $1$ : the filter trusts the sensor almost completely, because its own prediction is now very uncertain.
A wrong noise model. Set the sensor noise $\sigma$ to $1$ and the filter's $r$ to $0.1$ , so the filter believes the sensor is ten times better than it is. Question: what do the innovation chart and the readout innovations inside the 95% region show? What to see: the innovations jump far outside the violet $\pm 2\sqrt S$ band and the readout drops far below 95%. The filter is overconfident. Press set r = σ and watch it recover. (Try also $q$ very small with the back and forth target.)

3. How the filter works #

The model #

The state is $x = (p_x, p_y, v_x, v_y)$ : position and velocity. Between two measurements, $\Delta t$ seconds apart, the target moves with constant velocity plus a random acceleration. The sensor sees only the position:

\begin{aligned} x_k &= F x_{k-1} + w_k, & w_k &\sim \mathcal N(0, Q), \\ z_k &= H x_k + v_k, & v_k &\sim \mathcal N(0, R), \end{aligned}

F = \begin{pmatrix} I & \Delta t\, I \\ 0 & I \end{pmatrix},\qquad Q = q \begin{pmatrix} \tfrac{\Delta t^3}{3} I & \tfrac{\Delta t^2}{2} I \\ \tfrac{\Delta t^2}{2} I & \Delta t\, I \end{pmatrix},

H = \begin{pmatrix} I & 0 \end{pmatrix},\qquad R = r^2 I .

Here $I$ is the $2 \times 2$ identity. This is the constant-velocity model. The number $q$ (the process noise) says how strongly the velocity can change; $r$ (the measurement noise) says how noisy the sensor is. In the simulation $\Delta t = 0.1$ s.

Where the matrix

Q

comes from

Assume the acceleration is white noise $a(t)$ with spectral density $q$ . Over one step, the position changes by $\int_0^{\Delta t} s\, a(t_k - s)\, ds$ and the velocity by $\int_0^{\Delta t} a(t_k - s)\, ds$ (on top of the constant-velocity motion). The covariance of $(s, 1)\,a$ integrated over $[0, \Delta t]$ is $q \int_0^{\Delta t} \begin{pmatrix} s^2 & s \\ s & 1 \end{pmatrix} ds = q \begin{pmatrix} \Delta t^3/3 & \Delta t^2/2 \\ \Delta t^2/2 & \Delta t \end{pmatrix}$ , one block for each axis.

Predict #

Push the mean and the covariance through the model:

\hat x^-_k = F \hat x_{k-1}, \qquad P^-_k = F P_{k-1} F^\top + Q .

$FPF^\top$ moves and stretches the ellipse (position uncertainty grows with velocity uncertainty), and $+\,Q$ makes it larger. This is the growing violet ellipse.

Update #

Compare the measurement with the predicted measurement $H\hat x^-_k$ , then correct:

\begin{aligned} \nu_k &= z_k - H \hat x^-_k && \text{innovation} \\ S_k &= H P^-_k H^\top + R && \text{innovation covariance} \\ K_k &= P^-_k H^\top S_k^{-1} && \text{Kalman gain} \\ \hat x_k &= \hat x^-_k + K_k \nu_k, \qquad P_k = (I - K_k H) P^-_k . \end{aligned}

For a linear model with Gaussian noise, this gives the exact posterior: $p(x_k \mid z_1, \dots, z_k)$ is Gaussian with mean $\hat x_k$ and covariance $P_k$ . So $\hat x_k$ is the estimate with the smallest mean squared error. (The widget computes $P_k$ in the equivalent "Joseph form" $(I - KH)P^-(I-KH)^\top + KRK^\top$ , which stays symmetric and positive definite with rounding errors.)

Why the gain balances model and data #

Look at one coordinate with a direct position sensor ( $H = 1$ ). Then $S = P^- + R$ and

K = \frac{P^-}{P^- + R}, \qquad \hat x = (1 - K)\,\hat x^- + K z = \frac{R\,\hat x^- + P^- z}{P^- + R}, \qquad \frac{1}{P} = \frac{1}{P^-} + \frac{1}{R} .

The update is a weighted average of the prediction and the measurement. Each one gets a weight proportional to the other's variance, so the more certain source counts more. The precisions (inverse variances) add, so the result is more certain than either source alone.

A perfect sensor ( $R \to 0$ ) gives $K \to 1$ : copy the measurement.
A useless sensor ( $R \to \infty$ ) gives $K \to 0$ : keep the prediction.
A perfect model ( $Q = 0$ ) makes $P^-$ shrink step by step, so $K \to 0$ : the filter stops listening.

Multiplying $q$ , $r^2$ and the starting $P$ by the same number multiplies every covariance by that number and leaves $K$ unchanged. The steady state does not depend on the starting $P$ , so the steady-state gain depends only on the ratio $q / r^2$ : "how much do I trust the model compared with the sensor".

Small example. Prediction $\hat x^- = 10$ with $P^- = 3$ , measurement $z = 14$ with $R = 1$ . Then $K = 3/4$ , $\hat x = 10 + 0.75 \cdot (14 - 10) = 13$ and $P = (1 - 0.75) \cdot 3 = 0.75$ . The new variance $0.75$ is smaller than both $3$ and $1$ .

Quick check

A filter predicts $\hat x^- = 2$ with $P^- = 1$ . The sensor reads $z = 5$ with $R = 2$ . What is the updated estimate $\hat x$ ?

The filter can check itself #

If the model is right, the innovations are Gaussian with mean $0$ and covariance $S_k$ , and they are independent over time. So about 95% of them should lie in the 95% region $\nu_k^\top S_k^{-1} \nu_k \le 5.99$ (the 95% quantile of $\chi^2$ with 2 degrees of freedom). The readout innovations inside the 95% region counts exactly this. Far fewer than 95% means the filter is overconfident ( $q$ or $r$ too small); 100% for a long time means it is too cautious. The same test is used to monitor real trackers and weather models.

Quick check

The target enters the no-signal zone and no measurements arrive for 2 seconds. What happens to the covariance $P$ during this time?

4. A nonlinear sensor: EKF and particle filter #

A radar does not measure $x$ and $y$ . It measures the range $\rho$ (distance) and the bearing $\theta$ (angle) of the target:

z = h(x) + v, \qquad h(x) = \begin{pmatrix} \sqrt{p_x^2 + p_y^2} \\ \operatorname{atan2}(p_y, p_x) \end{pmatrix}, \qquad v \sim \mathcal N\!\big(0, \operatorname{diag}(\sigma_\rho^2, \sigma_\theta^2)\big).

The positions that fit one measurement form a curved band: a piece of a ring. A Gaussian cannot have this shape, so the Kalman filter is no longer exact. Two standard fixes:

The extended Kalman filter (EKF) replaces $h$ by its first-order Taylor expansion at the prediction: it uses the Jacobian $H_k = \partial h / \partial x$ at $\hat x^-_k$ in place of $H$ , and $h(\hat x^-_k)$ as the predicted measurement. With $\rho = \sqrt{p_x^2 + p_y^2}$ ,

H_k = \begin{pmatrix} p_x/\rho & p_y/\rho & 0 & 0 \\ -p_y/\rho^2 & p_x/\rho^2 & 0 & 0 \end{pmatrix}.

The angle part of the innovation must be wrapped to $(-\pi, \pi]$ .

The particle filter (bootstrap filter) represents the belief by $N$ samples $x^{(i)}$ with weights $w^{(i)}$ . Predict: move every particle with the model and its own random noise. Update: multiply each weight by the likelihood $p(z \mid x^{(i)})$ and normalize. When the effective sample size $N_\text{eff} = 1 / \sum_i (w^{(i)})^2$ falls below $N/2$ , resample: draw $N$ new particles in proportion to the weights, so unlikely particles die and likely ones are copied. The particle filter can represent any shape, and it becomes exact as $N \to \infty$ . The price is $N$ times more work.

Watch the particles bend into an arc, then pick other examples under Try. The yellow triangle is the radar. The orange band holds the positions that fit the current measurement (range $\pm 2\sigma_\rho$ , bearing $\pm 2\sigma_\theta$ ). Violet: the EKF estimate and its 95% ellipse. Aqua: the particles (bigger dots have larger weights) and their mean (ring). Both filters get the same measurements. The table compares their errors, how often their 95% ellipse contains the truth (for the particle filter: the ellipse of the particles' mean and covariance, not drawn), and the cost. Try wrong first guess: the EKF needs one or two seconds to find the target; the particles find it at once.

The banana. Start with banana (selected when the page opens): the range is very precise ( $\sigma_\rho = 0.03$ ) but the bearing is poor ( $\sigma_\theta = 20°$ ). Question: what shape does the particle cloud take, and does the EKF ellipse contain the truth about 95% of the time? What to see: the particles form a thin arc around the radar. The EKF ellipse is a straight, flat approximation of that arc. In our one-minute runs it contained the truth only about 35–55% of the time, and its error was about 1.5 times the particle filter's. The particle filter stays near 90–95%. (The table uses only the last 10 s, so its numbers move up and down; watch them for a while.)
How many particles? Pick few particles ( $N = 30$ ), then move $N$ up to a few thousand. Question: what happens to the effective sample size, the error and the time per step? What to see: with few particles the cloud collapses to a handful of points after each resampling and can lose the target. More particles give a smoother cloud and a smaller error, but the error stops improving at some point (the measurements limit it), while the cost keeps growing in proportion to $N$ .

Quick check

Why does the EKF ellipse often miss the truth in the banana example?

5. From tracking to weather forecasting #

Weather forecasting solves the same problem at a huge scale. The state $x$ is the whole atmosphere on a grid (temperature, wind, pressure and humidity at every point): hundreds of millions of numbers or more. The measurements are tens of millions of observations a day from satellites, weather stations, balloons, aircraft and ships. Combining a model forecast with observations is called data assimilation, and it uses the same words:

Kalman filter	Data assimilation
prediction $\hat x^-$ , covariance $P^-$	background (first guess) $x_b$ , background error covariance $B$
measurement $z$ , matrix $H$	observations $y$ , observation operator $\mathcal H$
innovation $z - H\hat x^-$	innovation, "observation minus background"
update $\hat x$	analysis $x_a$
predict step	forecast with the weather model, until the next cycle (every 6 or 12 hours)

The difficulty is size. With $n \approx 10^9$ state variables, $P$ would have $10^{18}$ entries: it cannot be stored, let alone multiplied by $F$ . Two families of methods avoid this:

The ensemble Kalman filter (EnKF) runs a few dozen forecasts (an ensemble) and uses their sample covariance in place of $P^-$ . This is a particle-like idea, but the update is still the Kalman update, not a reweighting.
4D-Var looks for the initial state $x_0$ that best fits all observations in a time window and the background, by minimizing

\begin{aligned} J(x_0) = {} & \tfrac12 (x_0 - x_b)^\top B^{-1} (x_0 - x_b) \\ & + \tfrac12 \sum_k \big(y_k - \mathcal H_k(x_k)\big)^\top R_k^{-1} \big(y_k - \mathcal H_k(x_k)\big), \end{aligned}

where $x_k$ is the model forecast from $x_0$ . The gradient comes from the adjoint model (reverse-mode differentiation of the forecast model). For a linear model with Gaussian errors and no model error, 4D-Var gives the same estimate at the end of the window as the Kalman filter.

Why not a particle filter? In high dimension the weights collapse: one particle gets almost all the weight. The number of particles needed grows exponentially with the effective dimension of the problem (Snyder and co-authors, 2008), so pure particle filters are not used for global weather models. In the widget above you can see the start of this problem with $N = 30$ in only 4 dimensions.

Quick check

A weather model has $n = 10^9$ state variables. Why can the forecast centre not run the Kalman filter equations exactly?

Key takeaways

The Kalman filter keeps a Gaussian belief (mean $\hat x$ , covariance $P$ ) and repeats two steps: predict $\hat x^- = F\hat x$ , $P^- = FPF^\top + Q$ ; update $\hat x = \hat x^- + K\nu$ , $P = (I - KH)P^-$ .
The innovation $\nu = z - H\hat x^-$ is the surprise in the measurement; its covariance is $S = HP^-H^\top + R$ .
The Kalman gain $K = P^- H^\top S^{-1}$ weights the measurement against the prediction. In one dimension $K = P^-/(P^- + R)$ : a precise sensor gives $K \to 1$ , a precise model gives $K \to 0$ .
The gain depends on $P^-$ and $R$ , not on the value of $z$ . For a fixed model it converges to a steady-state value that depends only on the ratio $q/r^2$ .
Without measurements only the predict step runs, so the uncertainty grows; the next measurement then gets a large gain.
For a linear-Gaussian model the Kalman filter gives the exact posterior. If the model is right, about 95% of the innovations fall inside the 95% region; far fewer means an overconfident filter.
For a nonlinear sensor the EKF linearizes $h$ with its Jacobian; a particle filter uses weighted samples and resampling, which is more general but needs many particles and fails in very high dimension.
Data assimilation in weather forecasting is filtering at a huge scale: the ensemble Kalman filter and 4D-Var replace the full covariance $P$ , which is too large to store.

Positive definite matrices and Cholesky: covariance matrices, ellipses, and why the posterior covariance is "smaller" than the prior one (the Loewner order).
QR and least squares: the update as a weighted least-squares problem, and square-root filters.
Jacobians, Hessians and Taylor: the linearization behind the EKF.
Gaussian integrals and Laplace's method: working with Gaussians.
State-space models: the same linear recurrence $x_k = Ax_{k-1} + Bu_k$ as a deep-learning layer.
Probability and Statistics: the multivariate Gaussian, Bayesian inference, and Monte Carlo with importance sampling (the idea behind particle weights).
ML for Science: a full lesson on data assimilation, the Kalman filter and 4D-Var.
Generative models: diffusion models used for data assimilation.

1. The tracking simulation #

2. Try this #

3. How the filter works #

The model #

Predict #

Update #

Why the gain balances model and data #

The filter can check itself #

4. A nonlinear sensor: EKF and particle filter #

5. From tracking to weather forecasting #

6. Related lessons #