Kalman Filter

Kalman Filter

The Kalman filter is the closed-form recursive Bayesian filter for the linear Gaussian state-space model. Given a hidden state $x_t\in {\mathbb{R}}^p$ that evolves as $x_t=\Phi x_{t-1}+w_t$ with $w_t\sim \mathcal{N}(0,Q)$, observed through $y_t=A_t{x}_t+v_t$ with $v_t\sim \mathcal{N}(0,R)$, the filter produces the Gaussian posterior $p(x_t\mid y_{1:t})=\mathcal{N}(x_t^t,P_t^t)$ at every time step using only the previous step’s posterior and the new observation.

Each step splits into two operations. The prediction step propagates the previous posterior forward through the dynamics, producing the one-step-ahead prior on the state before seeing $y_t$:
$x_t^{t-1}=\Phi x_{t-1}^{t-1},P_t^{t-1}=\Phi P_{t-1}^{t-1}{\Phi }^{\top }+Q.$
The mean is updated by the deterministic dynamics; the covariance is propagated by the same dynamics and inflated by the process noise $Q$. Uncertainty about the state grows during prediction because the random shock $w_t$ adds variance.

The update step then conditions on the new observation $y_t$, applying the standard Gaussian conditioning identity to combine the prior $\mathcal{N}(x_t^{t-1},P_t^{t-1})$ with the likelihood $\mathcal{N}(y_t\mid A_t{x}_t,R)$:
$x_t^t=x_t^{t-1}+K_t(y_t-A_t{x}_t^{t-1}),P_t^t=(I-K_t{A}_t)P_t^{t-1},$
where the Kalman gain is
$K_t=P_t^{t-1}{A}_t^{\top }[A_t{P}_t^{t-1}{A}_t^{\top }+R{]}^{-1}.$
The gain is the Bayesian-conjugacy weight that determines how much the new observation shifts the prior mean. The quantity ${\nu }_t=y_t-A_t{x}_t^{t-1}$ is the innovation: the part of the observation that the prediction did not anticipate.

The whole recursion runs forward in $t$, starting from the initial state $x_0\sim \mathcal{N}({\mu }_0,{\Sigma }_0)$. At every step the cost is $O(p^3)$ in the state dimension (dominated by the matrix inverse inside the Kalman gain), independent of how much past data has accumulated.

Linear-Gaussian Assumption linear dynamics and observations with Gaussian noise. When either assumption breaks, exact inference is no longer Gaussian and approximations are needed: the Extended Kalman Filter (EKF) linearizes non-linear dynamics around the current estimate, the Unscented Kalman Filter (UKF) propagates a small set of sample points through the non-linearity, and the particle filter drops Gaussianity entirely in favor of a Monte Carlo posterior. All three reduce to the standard Kalman filter when the model is exactly linear-Gaussian.

The closed-form recursion only applies to

Intuition

The Kalman filter is conjugate Bayesian inference applied one observation at a time. The prior at the start of step $t$ is the posterior from step $t-1$ propagated forward through the dynamics; the likelihood for step $t$ is the Gaussian density of the new observation given the state; and the posterior is the Gaussian conjugate-update of those two ingredients. The remarkable fact about the linear-Gaussian setting is that the posterior is also Gaussian, so the same machinery applies at the next step without any approximation. The filter is therefore the time-series analogue of Bayesian linear regression, with the static parameter $\beta$ replaced by a state $x_t$ that evolves over time.

The two-step prediction-update structure makes the Bayesian story explicit. The prediction step does not look at $y_t$ at all; it just asks “where would I expect the state to be at time $t$ given everything I knew at time $t-1$?”, propagating both the mean and the uncertainty through the dynamics. The update step then absorbs the new observation, shifting the prior mean toward what $y_t$ suggests by an amount controlled by the Kalman gain $K_t$. The gain is the relative-trust ratio between the prediction and the measurement: if the measurement noise $R$ is large compared to the predicted state covariance $A_t{P}_t^{t-1}{A}_t^{\top }$, the gain is small and the prior is barely moved; if the measurement noise is small (a precise sensor) the gain is close to $A_t^{-1}$ (or its right pseudo-inverse) and the prior is replaced by the measurement. This automatic re-weighting between prior knowledge and new evidence is the Bayesian update made operational.

Properties

(Two-Step Recursion) Each filter step is a prediction propagating the posterior forward, followed by an update conditioning on the new observation.

The prediction step uses only the dynamics $(\Phi ,Q)$ and the previous posterior; it produces the prior $\mathcal{N}(x_t^{t-1},P_t^{t-1})$ at time $t$. The update step uses only the observation model $(A_t,R)$ and the new $y_t$; it produces the posterior $\mathcal{N}(x_t^t,P_t^t)$. Splitting the recursion this way is what makes it computationally cheap (no need to revisit past data) and conceptually clean (prior is propagated then reconditioned).

(Kalman Gain as Trust Ratio) $K_t$ is the optimal weight between the prediction and the new observation.

The gain $K_t=P_t^{t-1}{A}_t^{\top }(A_t{P}_t^{t-1}{A}_t^{\top }+R{)}^{-1}$ has the form (prior covariance × measurement Jacobian) divided by (predicted measurement covariance + noise covariance). Two limiting cases make the meaning concrete: in the high-noise limit $R\to \infty$, the gain $K_t\to 0$ and the update degenerates to $x_t^t=x_t^{t-1}$, so a worthless measurement does not move the prior. In the low-noise limit $R\to 0$ with $A_t$ invertible, the gain $K_t\to A_t^{-1}$ and the update becomes $x_t^t=A_t^{-1}{y}_t$, so a perfect measurement overrides the prior entirely. Between those extremes the gain is the optimal Bayesian compromise.

(Innovation) The residual ${\nu }_t=y_t-A_t{x}_t^{t-1}$ is the new information in $y_t$.

The innovation is what the prediction got wrong: the part of the observation that the dynamics did not already explain. Two consequences flow from this. First, the update equation $x_t^t=x_t^{t-1}+K_t{\nu }_t$ adjusts the prior by the Kalman-weighted innovation, so the size of the correction is set by how surprising the observation was. Second, when the model is correctly specified, the innovation sequence $\{{\nu }_t\}$ is white noise (mean zero, uncorrelated across time) with covariance $A_t{P}_t^{t-1}{A}_t^{\top }+R$. This innovation whiteness is the standard model diagnostic: non-white innovations indicate that the dynamics, the observation matrix, or the noise covariances are misspecified.

(Likelihood Computation) The filter produces the model likelihood as a by-product.

Each innovation has a known Gaussian density under the model, so the joint likelihood of the observed data factorizes into a product of one-step-ahead predictive densities,
$\log p(y_{1:T}\mid \theta )={\sum }_{t=1}^T\log \mathcal{N}\left(y_t\right|A_t{x}_t^{t-1},A_t{P}_t^{t-1}{A}_t^{\top }+R).$
The Kalman filter computes every term in this sum in passing, so likelihood evaluation costs no more than running the filter. This is how statsmodels evaluates ARIMA likelihoods (cast as state-space models) and how unknown parameters $(\Phi ,Q,R)$ are estimated by maximum likelihood on top of the filter.

(Cost is $O(p^3)$ Per Step) The filter runs in time independent of how much data has accumulated.

The dominant cost at each step is the inverse of the $q\times q$ matrix inside the Kalman gain, where $q$ is the observation dimension; the rest of the operations are matrix products at $O(p^3)$ in the state dimension. Crucially, the recursion does not revisit any past observation: all the history is summarized by the current $(x_t^t,P_t^t)$ pair. So the total cost of running the filter on a length-$T$ record is $O(T{p}^3)$, not $O(T^2)$ or $O(T^3)$, which is what makes it practical for online use on long records.

(Steady State) For a time-invariant model, the covariance $P_t^t$ converges to a fixed point as $t$ grows.

When $\Phi ,A,Q,R$ do not depend on $t$ and the system is stable, the recursion $P_t^t=(I-K_{t}A)P_t^{t-1}$ with $P_t^{t-1}=\Phi P_{t-1}^{t-1}{\Phi }^{\top }+Q$ converges to the unique solution of the discrete algebraic Riccati equation. In steady state the gain $K_t$ also becomes constant, so the filter reduces to a fixed linear filter on the innovations, useful for analytical work and for fast online implementations that precompute the steady-state gain.

(Missing Data is Free) Skip the update step when no observation is available.

If $y_t$ is missing at time $t$, the filter performs only the prediction step and carries the prior forward. The covariance $P_t^t=P_t^{t-1}$ is larger than it would be after an update; the filter is honest that no new information arrived. When the next observation comes in at time $t^{\prime }>t$, the prediction step is repeated $t^{\prime }-t$ times to bring the prior up to date, then the update step uses $y_{t^{\prime }}$ as usual. This handles arbitrary patterns of missing data without any special-purpose code.

Examples

Local-level model on noisy sensor data

You have a sensor reading the true value of a slowly drifting quantity, with both sensor noise and slow random changes in the truth. Model: $x_t=x_{t-1}+w_t$ with $w_t\sim \mathcal{N}(0,q)$, observation $y_t=x_t+v_t$ with $v_t\sim \mathcal{N}(0,r)$.

One filter step $t-1$ the posterior is $\mathcal{N}(10,0.5)$, and the new observation is $y_t=12$ with $q=0.1$ and $r=1$.

Suppose at time

Prediction: $x_t^{t-1}=10$ (mean unchanged because $\Phi =1$), $P_t^{t-1}=0.5+0.1=0.6$.

Kalman gain: $K_t=0.6/(0.6+1)=0.375$.

Update: innovation ${\nu }_t=12-10=2$, $x_t^t=10+0.375\cdot 2=10.75$, $P_t^t=(1-0.375)\cdot 0.6=0.375$.

The new estimate is closer to the observation than to the prior, reflecting that the sensor noise variance ($r=1$) is somewhat larger than the prior variance ($P_t^{t-1}=0.6$) but not overwhelmingly so. If the sensor were ten times noisier ($r=10$), the gain would be $0.057$ and the estimate would barely budge from the prior. If the sensor were ten times cleaner ($r=0.1$), the gain would be $0.857$ and the estimate would be pulled almost all the way to the observation.

Tracking a moving target

A radar measures the position of a vehicle moving in 1D at unknown velocity. State $x_t=({\text{position}}_t,{\text{velocity}}_t{)}^{\top }$ with constant-velocity dynamics, observation is position only.

Setup and what the filter learns $\Phi =\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ (position += velocity each step, velocity unchanged), with process noise $Q$ allowing small acceleration. Observation: $A=(1,0)$ (position observed, velocity hidden), with measurement noise $R$.

Dynamics:

The filter learns the velocity implicitly by observing how position changes over time. Even though velocity is never measured directly, the cross-covariance entries of $P_t^t$ pick up the correlation between estimated position and estimated velocity, and after several observations the velocity estimate becomes much sharper than the prior. This is the classical demonstration that the Kalman filter does sensor fusion across time: indirect information about hidden quantities accumulates by way of their dynamic coupling to observed quantities.

Online ARIMA likelihood evaluation

Why does statsmodels.tsa.arima.model.ARIMA(...).fit() not require $O(T^2)$ memory or $O(T^3)$ time?

Solution $O(T{p}^3)$ where $p$ is the state dimension (small, $\le \max (p,q+1)$ for ARMA(p, q)). Each filter step produces one innovation ${\nu }_t$ and its variance, contributing one term to the log-likelihood sum. The maximum-likelihood optimizer wraps a numerical optimizer around this filter-based likelihood evaluation. For an ARMA(2, 1) on a record of $T=10^4$ observations, the state has dimension $3$, the per-step cost is $\sim 27$ flops, and the total likelihood evaluation is microseconds, fast enough that the optimizer can do thousands of evaluations during the fit.

An ARIMA model can be written in state-space form (a state vector containing the necessary lags), and the Kalman filter then evaluates the model likelihood in

Derivation

The Kalman update is a direct application of the Gaussian conditioning identity. At time $t$ the prior is $x_t\sim \mathcal{N}(x_t^{t-1},P_t^{t-1})$ from the prediction step, and the observation given the state is $y_t\mid x_t\sim \mathcal{N}(A_t{x}_t,R)$. The joint distribution of $(x_t,y_t)$ given the past is Gaussian with mean $(x_t^{t-1},A_t{x}_t^{t-1})$ and covariance
$\left(\begin{array}{cc}{P}_t^{t-1}& P_t^{t-1}{A}_t^{\top }\\ A_t{P}_t^{t-1}& A_t{P}_t^{t-1}{A}_t^{\top }+R\end{array}\right).$

Applying the Gaussian conditioning formula (see 6.2 Multivariate Gaussian Distribution) for $x_t$ given $y_t$ produces
$x_t\mid y_{1:t}\sim \mathcal{N}(x_t^{t-1}+K_t(y_t-A_t{x}_t^{t-1}),(I-K_t{A}_t)P_t^{t-1}),$
with $K_t=P_t^{t-1}{A}_t^{\top }(A_t{P}_t^{t-1}{A}_t^{\top }+R{)}^{-1}$, exactly the update equation. The Kalman gain is therefore not a separate concept to memorize but the cross-covariance-times-inverse-marginal-covariance term of the standard conditioning formula, specialized to this model.

The prediction step follows the same logic propagated through the dynamics. If $x_{t-1}\mid y_{1:t-1}\sim \mathcal{N}(x_{t-1}^{t-1},P_{t-1}^{t-1})$ and $x_t=\Phi x_{t-1}+w_t$ with $w_t\sim \mathcal{N}(0,Q)$ independent of the past, then $x_t\mid y_{1:t-1}$ is the linear-transformation-plus-noise of a Gaussian, which is again Gaussian with mean $\Phi x_{t-1}^{t-1}$ and covariance $\Phi P_{t-1}^{t-1}{\Phi }^{\top }+Q$. So the prediction step is also nothing but the standard rule for the distribution of a linear function of a Gaussian random variable.

The whole recursion is therefore one Gaussian conjugacy step (prediction) followed by one Gaussian conditioning step (update), repeated forever. The Kalman gain and the prediction-update structure are presentation choices; the math underneath is the same conjugate-update story as Normal-Normal Bayesian inference, extended to handle a state that evolves between observations.

See Also

• 3.12 Kalman Filtering: section index, when filter vs. smoother
• 3.12.2 Kalman Smoother: backward pass for retrospective state estimation
• 2.6.2 Dynamic Linear Model: the time-series model the filter operates on
• 6.2 Multivariate Gaussian Distribution: the conjugate-update identity at the heart of the recursion
• 3.8.1 Bayesian Linear Regression: the static analog (one-shot Bayesian regression with a Gaussian prior)
• 3.10.2 GP Regression: a different closed-form Gaussian posterior; Kalman is its temporal-state-space special case
• 3.11.5 EM Algorithm: used to learn unknown $\Phi ,Q,R$ when they are not given (E-step is the smoother)