This document derives the discrete-time linear Kalman filter from first
principles. The derivation establishes what the filter is, why it works,
and what it assumes. The reference implementation in
kalman_filter.py is a direct expression of the
mathematics here.
Many systems of engineering interest share a common structure. An underlying state evolves over time according to known dynamics. That state is observed through measurements that are noisy, indirect, or both. The state itself is hidden. What is available are the measurements and a model of how the state and measurements relate.
The state estimation problem is to recover the best estimate of the hidden state from the sequence of measurements observed so far. "Best" must be defined precisely. The answer depends on what assumptions hold about the system and the noise.
Examples that fit this structure:
- Tracking a moving object whose position and velocity must be inferred from noisy position measurements
- Estimating the orientation of a spacecraft from gyroscope and star tracker readings
- Recovering a signal from a noisy sensor whose dynamics are known
- Estimating the parameters of a slowly time-varying system from measurements of its outputs
In each case, the state is what we want to know. The measurements are what we have. The dynamics and measurement model are what we assume.
The Kalman filter solves this problem under three specific assumptions.
Time is discrete. The state evolves in steps:
The dynamics and measurement model are linear. The state at time
The noise is Gaussian. Both the process noise and the measurement noise are Gaussian with known covariance. The process noise represents uncertainty in the dynamics. The measurement noise represents uncertainty in observations.
Under these three assumptions, the optimal state estimator has a closed-form recursive structure. That structure is the Kalman filter.
The problem this document derives a solution to:
Given a sequence of measurements
$z_1, z_2, \ldots, z_k$ and a model of how the state evolves and how measurements relate to the state, compute the conditional mean and covariance of the state at time$k$ given all measurements through time$k$ .
The conditional mean is the best estimate in a sense made precise in Section 6. The conditional covariance quantifies the uncertainty remaining in that estimate.
The assumptions this derivation depends on:
- The state evolves according to a linear process model with additive Gaussian process noise (Section 2.1)
- Measurements are a linear function of the state with additive Gaussian measurement noise (Section 2.2)
- The process noise and measurement noise are mutually independent, white, and have known covariance matrices (Section 2.3)
- The initial state is Gaussian with known mean and covariance
These assumptions are restrictive. Many real systems violate them. The Kalman filter remains useful in those cases as an approximation and as the foundation for more general filters. Those extensions are out of scope here. The derivation that follows holds exactly under the assumptions above.
The state of the system at time
where
The state transition matrix
The process noise
The state
where
The measurement matrix
The measurement noise
The process noise and measurement noise are assumed to be Gaussian with zero mean and known covariance:
where
Zero mean. The noise has no systematic bias. Any bias in the
dynamics or measurements is assumed to be modeled in
Known covariance. The covariance matrices
Whiteness. The noise is uncorrelated across time:
where
Mutual independence. The process noise and measurement noise are independent of each other at all times:
Initial state. The initial state
The initial state is independent of all process and measurement noise.
These assumptions are restrictive. Real systems violate them in specific, characterizable ways. Section 7 develops the diagnostics that detect when the assumptions hold and when they fail.
The notation used throughout this derivation:
| Symbol | Meaning | Dimension |
|---|---|---|
| True state at time |
||
| Estimated state at time |
||
| Predicted state at time |
||
| State estimate covariance at time |
||
| Predicted state covariance at time |
||
| State transition matrix | ||
| Process noise covariance | ||
| Measurement at time |
||
| Measurement matrix | ||
| Measurement noise covariance | ||
| Process noise | ||
| Measurement noise | ||
| Innovation (defined in Section 5.1) | ||
| Innovation covariance (defined in Section 5.1) | ||
| Kalman gain (defined in Section 5.2) | ||
| State dimension | scalar | |
| Measurement dimension | scalar |
State estimates are distinguished from true state by the hat:
The transition between predicted and updated quantities is the heart of the filter. The next sections derive that transition.
The state estimation problem can be stated in Bayesian terms. At time
This distribution captures everything that can be known about the state
at time
The recursive structure comes from a simple observation. The posterior
at time
The recursion proceeds in two steps:
The prediction step takes the posterior from the previous time step forward through the dynamics, producing a prior at the current time step. The update step incorporates the new measurement, producing the new posterior. Each step has a precise mathematical form derived in the sections that follow.
The prediction step is an application of the law of total probability.
Given the posterior at time
The integral marginalizes over the previous state. The transition
density $p(\mathbf{x}k \mid \mathbf{x}{k-1})$ encodes the process
model. The result is the distribution of
The update step is an application of Bayes' rule. Given the predicted
distribution and the measurement model from Section 2.2, the posterior
after observing
The likelihood
Equations (3.3) and (3.4) are general. They hold for any process and measurement model with well-defined transition and likelihood densities. The Kalman filter is what these equations become under the linear-Gaussian assumptions of Section 2.
The integrals and ratios in equations (3.3) and (3.4) are generally
intractable. For arbitrary process and measurement models, the
posterior at time
The linear-Gaussian case is the exception. Under the assumptions of Section 2:
- The transition density $p(\mathbf{x}k \mid \mathbf{x}{k-1})$ is Gaussian
- The likelihood
$p(\mathbf{z}_k \mid \mathbf{x}_k)$ is Gaussian - The initial distribution
$p(\mathbf{x}_0)$ is Gaussian
Two facts about Gaussian distributions make the recursion close in closed form.
Linear transformations of Gaussians are Gaussian. If
Conditional distributions of jointly Gaussian variables are Gaussian.
If
The combination of these two facts means that if the posterior at
time
A Gaussian distribution is fully characterized by its mean and covariance. The recursion therefore reduces from "propagate a distribution" to "propagate two quantities: a mean vector and a covariance matrix." That reduction is what makes the Kalman filter computationally tractable.
The sections that follow derive the explicit recursions for the mean and covariance. Section 4 derives the prediction step. Section 5 derives the update step. Section 6 establishes the optimality properties that hold under the linear-Gaussian assumptions.
The prediction step propagates the state estimate forward through the
dynamics. Starting from the posterior at time
The predicted state at time
Substituting the process model from equation (2.1):
Expectation is linear. The process noise
The first expectation is the posterior mean from time
The predicted state is the previous state estimate propagated through the state transition matrix. No measurement information has been used. The dynamics alone determine the predicted state.
The predicted covariance is the conditional covariance of
Substituting the process model and the predicted mean from equation (4.5):
The error in the predicted state has two contributions: the propagated error from the previous estimate, and the new process noise. Both are zero-mean. Substituting equation (4.7) into equation (4.6) and expanding the outer product:
- \mathbb{E}\left[\mathbf{F}k(\mathbf{x}{k-1} - \hat{\mathbf{x}}_{k-1}) \mathbf{w}k^T \mid \mathbf{z}{1:k-1}\right] $$ $$
- \mathbb{E}\left[\mathbf{w}k (\mathbf{x}{k-1} - \hat{\mathbf{x}}_{k-1})^T \mathbf{F}k^T \mid \mathbf{z}{1:k-1}\right] $$ $$
- \mathbb{E}\left[\mathbf{w}_k \mathbf{w}k^T \mid \mathbf{z}{1:k-1}\right] \tag{4.8} $$
The two cross terms vanish. The process noise $\mathbf{w}k$ is independent of $\mathbf{x}{k-1}$ and of all prior measurements; the expectation of the product factors, and one factor is zero. The remaining terms are the propagated covariance and the process noise covariance:
The predicted covariance has two terms. The first term, $\mathbf{F}k
\mathbf{P}{k-1} \mathbf{F}_k^T$, is the prior covariance transformed
by the dynamics. The second term,
Equations (4.5) and (4.9) give the mean and covariance of the predicted state. Because the dynamics are linear and the noise is Gaussian, the predicted state distribution is itself Gaussian:
This is the result of the marginalization integral in equation (3.3) under linear-Gaussian assumptions. The integral does not need to be evaluated explicitly. The Gaussian closure property from Section 3.3 guarantees the result.
The predicted distribution carries everything the dynamics know about
the state at time
The next section incorporates the measurement.
When the measurement
The innovation captures what the measurement adds beyond what was already predicted. If the predicted state were exact, the innovation would be zero. The innovation is nonzero because of two sources: the error in the predicted state, and the measurement noise.
Substituting the measurement model from equation (2.2) and the predicted state from Section 4:
The first term is the prediction error projected through the measurement matrix. The second term is the measurement noise. Both are zero-mean, so the innovation has zero mean under the model assumptions:
The innovation covariance is:
Substituting equation (5.2) and expanding:
The cross terms vanish because the measurement noise is independent
of the prediction error. The first remaining term is
The innovation covariance has two terms. The first term is the prediction uncertainty projected into measurement space. The second term is the measurement noise. Both are uncertainty contributions to the difference between predicted and observed measurements.
The properties of the innovation sequence are central to filter diagnostics. Section 7 develops them in detail.
The updated state estimate is a linear combination of the predicted state and the innovation:
The matrix
The updated covariance is:
Substituting the update equation (5.7):
Substituting the innovation from equation (5.2):
The updated error is a linear combination of the prediction error and the measurement noise. Substituting into the covariance definition in equation (5.8) and expanding the outer product:
The cross terms vanish by the independence of the measurement noise
and prediction error. Equation (5.11) gives the updated covariance as
a function of the choice of
The Kalman gain is the choice of
Differentiating the trace of equation (5.11) with respect to
Rearranging:
The matrix on the left is the innovation covariance
The Kalman gain weighs the prediction uncertainty against the
innovation uncertainty. The numerator
Substituting the optimal gain from equation (5.14) into the covariance expression in equation (5.11) and simplifying produces the standard form of the updated covariance:
The updated covariance is the predicted covariance reduced by the
information contributed by the measurement. The factor
The updated state estimate from equation (5.7), the updated covariance
from equation (5.15), and the Gaussian closure property from Section
3.3 give the posterior distribution at time
This is the same result that would be obtained by applying the
Gaussian conditioning formula (Appendix B) directly to the joint
distribution of
Equation (5.11) gave the updated covariance as a function of any gain
Numerically they are not.
The standard form
The Joseph form preserves positive-definiteness:
Both terms in equation (5.17) are symmetric positive-semi-definite products. Their sum is symmetric positive-semi-definite by construction. The Joseph form is numerically robust even when the gain is slightly suboptimal due to rounding error or covariance specification mismatch.
The reference implementation uses the Joseph form. The standard form is mathematically cleaner; the Joseph form is what production estimation deploys.
The Kalman gain in equation (5.14) was derived by minimizing the trace of the updated covariance. The trace is the sum of the variances of the state estimate components. Minimizing it minimizes the total mean squared error of the estimate:
The Kalman filter is the minimum mean squared error (MMSE) estimator within the class of linear estimators. No linear combination of the prediction and the measurement produces a smaller mean squared error.
Under the linear-Gaussian assumptions of Section 2, a stronger statement holds. The Kalman filter is the MMSE estimator within the class of all estimators, linear or otherwise. The linear restriction is not a restriction at all when the underlying distributions are Gaussian.
The reason is the Gaussian conditioning property. When
This is the strongest optimality claim available. Under linear-Gaussian assumptions, the Kalman filter is not just the best linear estimator. It is the best estimator.
The minimum-variance derivation in Section 5.2 produces the optimal gain through calculus. The orthogonality principle produces the same gain through a geometric argument. Both paths arrive at the same result. Seeing both clarifies the structural reason for the optimality.
The orthogonality principle states that the optimal estimation error
is uncorrelated with the data used to form the estimate. Formally,
for the optimal
The error of the optimal estimate is orthogonal to every measurement used in computing the estimate. If the error were correlated with any measurement, that correlation could be exploited to reduce the error further. The estimate would not be optimal. Optimality requires the correlation to vanish.
Applying the orthogonality condition to the innovation:
Substituting the updated estimate from equation (5.7) and the innovation
from equation (5.2) into equation (6.3), then solving for
The orthogonality principle is geometric. The optimal estimate
This view does not change the equations. It changes how the equations are understood.
The optimality of the Kalman filter is conditional. The conditions are the assumptions of Section 2:
- Linear dynamics and measurements
- Gaussian noise with known covariance
- Process noise and measurement noise mutually independent and white
- Initial state Gaussian with known mean and covariance
When all four conditions hold, the filter is the MMSE estimator and no improvement is possible. When any condition is weakened, the optimality claim weakens with it.
Nonlinear dynamics or measurements. The Extended Kalman Filter linearizes the dynamics or measurement model around the current estimate and applies the linear Kalman update to the linearized system. The result is an approximation. It is no longer optimal in any formal sense, though it is often the best tractable approximation available. The Unscented Kalman Filter uses a deterministic sampling approach to propagate the mean and covariance through the nonlinear functions directly. It typically achieves better accuracy than the EKF for strongly nonlinear systems, but it too is an approximation.
Non-Gaussian noise. When the noise distribution is non-Gaussian, the Kalman filter remains the best linear estimator but is no longer the best estimator overall. Particle filters and other Monte Carlo methods can outperform the Kalman filter in this regime by representing the non-Gaussian posterior explicitly.
Misspecified covariance. The filter assumes
Correlated noise. When the process and measurement noises are correlated, or when either is colored rather than white, the standard Kalman filter is no longer optimal. Modified forms of the filter exist that handle these cases when the correlation structure is known.
Optimality is a property of the model, not a property of reality. The filter is optimal given the model. Whether the model fits reality is a separate question. The diagnostics in Section 7 provide tools to assess that question quantitatively.
This is the correct framing for production deployment. The filter is not magic. It is the best estimator under specific assumptions. The work of an estimation engineer is to determine whether those assumptions hold, to characterize how they fail when they do, and to deploy the filter with full knowledge of both.
The innovation sequence
The innovation sequence is white. Innovations at different times are mutually uncorrelated:
The whiteness property follows from the optimality of the Kalman
filter. The orthogonality principle from Section 6.2 states that the
optimal estimation error is uncorrelated with every measurement used
in computing the estimate. The innovation at time
Combining these: the innovation at time
The whiteness of the innovation sequence is the signature of optimal filtering. A correctly specified filter produces a white innovation sequence. A misspecified filter does not.
The innovation has zero mean:
This was established in equation (5.3). The derivation is direct. The innovation is the difference between the actual measurement and the predicted measurement:
Both terms have zero mean. The prediction error has zero mean because
the predicted state is the conditional mean of
A nonzero innovation mean indicates a bias in the filter's
predictions. The cause is structural: either the dynamics model
The innovation covariance equals
This was established in equation (5.6). The innovation covariance is
fully determined by the prediction covariance
The empirical innovation covariance, computed from the observed
innovation sequence, should agree with the filter-computed
The normalized innovation squared (NIS) statistic operationalizes this comparison:
Under the model assumptions,
The three innovation properties are whiteness, zero mean, and known covariance. They are jointly necessary and sufficient for the filter to be operating correctly under its specified model. When all three hold in the observed data, the model and the filter agree. When any fails, the model and the data disagree in a specific way:
Non-white innovations indicate that the filter is not extracting all available information from the measurements. The dynamics model or measurement model is missing structure that the data contains. This manifests as autocorrelation in the innovation sequence at one or more lags. The lag structure of the autocorrelation often points to the missing model component.
Non-zero mean innovations indicate bias in the filter's predictions.
The structural causes are model error in
Innovation covariance mismatch indicates that
The innovation sequence is therefore a self-diagnosing structure. It
contains within itself the information needed to detect when the
filter is operating outside its assumptions. The diagnostics that
extract this information are developed in the implementation in
diagnostics.py.
This is the structural reason for caring about innovation properties in production estimation. A filter that runs without monitoring its innovation sequence is operating blind. A filter that monitors its innovation sequence knows when it is performing correctly and when it is not. The work of an estimation engineer is to deploy the latter.
The Kalman filter is a recursive estimator with three operational phases: initialization, prediction, and update. Sections 4 and 5 derived the equations for prediction and update. Section 7 established the statistical properties that govern correct operation. This section consolidates the result into a complete algorithm.
The filter requires an initial state estimate and an initial covariance:
The initial estimate
When prior information is strong,
The filter is sensitive to initialization for the first several measurements. After enough measurements have been processed, the effect of the initialization fades. The filter converges to estimates that depend primarily on the dynamics, the measurements, and the noise covariances.
The process and measurement noise covariances
The prediction step propagates the state estimate and its covariance forward through the dynamics:
The predicted state is the previous estimate propagated through the state transition matrix. The predicted covariance is the previous covariance propagated through the same matrix, plus the additional uncertainty introduced by the process noise.
The prediction step requires no measurement. It can be applied at each time step regardless of whether a measurement is available. When measurements arrive irregularly, the filter can predict forward through multiple steps before incorporating the next measurement.
The update step incorporates a new measurement into the state estimate. It begins with the innovation:
The innovation covariance follows from the prediction covariance and the measurement noise covariance:
The Kalman gain weighs the prediction uncertainty against the innovation uncertainty:
The updated state estimate combines the prediction with the innovation, weighted by the gain:
The updated covariance uses the Joseph form for numerical robustness:
The update step requires a measurement. When no measurement is
available at time
The complete algorithm in pseudocode:
Inputs:
F[k], Q[k] # process model at each time step
H[k], R[k] # measurement model at each time step
z[k] # measurements at each time step
x_hat_0, P_0 # initial state and covariance
Initialize:
x_hat = x_hat_0
P = P_0
For k = 1, 2, ...:
# Predict
x_pred = F[k] @ x_hat
P_pred = F[k] @ P @ F[k].T + Q[k]
if measurement z[k] is available:
# Compute innovation and its covariance
nu = z[k] - H[k] @ x_pred
S = H[k] @ P_pred @ H[k].T + R[k]
# Compute Kalman gain
K = P_pred @ H[k].T @ inverse(S)
# Update state estimate
x_hat = x_pred + K @ nu
# Update covariance (Joseph form)
I_KH = I - K @ H[k]
P = I_KH @ P_pred @ I_KH.T + K @ R[k] @ K.T
# Diagnostic: record innovation and its statistics
record(nu, S)
else:
# No measurement; carry prediction forward
x_hat = x_pred
P = P_pred
output(x_hat, P)
The reference implementation in kalman_filter.py
follows this structure directly. The diagnostic recording step feeds
the innovation sequence analysis tools in
diagnostics.py developed from the properties in
Section 7.
The complete recursion is contained in equations (8.2) through (8.8). Given the inputs and initial conditions, the filter produces estimates that are optimal under the assumptions of Section 2 and self-diagnosing through the innovation sequence developed in Section 7.