Kalman filters

Idea: A number nobody can read

Latency drifts through the day, and you only see pings: the truth plus jitter.

• A single ping is too noisy
• A long average lags behind every shift
• A Kalman filter gives the best estimate now

Formula: State and reading

$x_t=F{x}_{t-1}+w_t,y_t=H{x}_t+v_t$

Process noise Q says how fast the state moves; measurement noise R how bad a reading is.

Formula: Predict

${\hat{x}}^{-}=F\hat{x},P^{-}=F^{2}P+Q$

Roll the estimate forward; its uncertainty grows by Q.

Formula: Correct

$K=\frac{P^{-}}{P^{-}+R},\hat{x}={\hat{x}}^{-}+K(y-{\hat{x}}^{-})$

Believe the share K of the surprise y − x̂⁻, then P = (1 − K) P⁻.

Example: The first ping

Start at $\hat{x}=40$ with $P=3$, and take $Q=1$, $R=12$. A ping reads $52$. What is the new estimate?

1. Predict: $P^{-}=3+1=4$
2. Gain $\frac{4}{4+12}=\frac{1}{4}$
3. $P$ returns to $3$; estimate $40+\frac{1}{4}\times 12=43$

Quick check: The second ping

Continue from that estimate. The next ping reads $38$. What is the estimate now?

Idea: The gain is a precision share

Correcting is Bayes’ rule: precisions add, $\frac{1}{4}+\frac{1}{12}=\frac{1}{3}$, so $P=3$.

• Mean: $\frac{3\times 40+1\times 52}{4}=43$
• Exact for linear models with Gaussian noise
• Otherwise still the best linear estimator

Common mistake: Mixing up the noises

A larger $R$ means bad readings, so the gain falls. A larger $Q$ means a fast state, so it rises.

Instead And use $P^{-}$, not $P$: skipping predict gives $\frac{3}{3+12}=\frac{1}{5}$, not $\frac{1}{4}$.

Idea: The steady state

Variances ignore the readings and settle at a fixed point: $\frac{R}{Q}=\frac{1-K}{K^2}$.

• Check: $\frac{1-\frac{1}{4}}{\frac{1}{4}\times \frac{1}{4}}=12$
• At a fixed gain it is an exponential moving average
• Choosing a decay secretly chooses $\frac{R}{Q}$

Idea: Say it in the room

Recite predict and correct, and name what each noise controls.

• The gain is a precision share
• Several dimensions: $P^{-}=FP{F}^T+Q$
• At steady state the filter is an exponential average