Source-linked AI summary
A simple derivation of the Kalman filter
Marco Chiani, Giovanni Petris, Moe Z. Win
TL;DR
The note addresses estimating the internal state of a discrete-time linear system, responding to expositions that omit detailed derivations. It presents a concise, self-contained derivation of the Kalman filter equations using least-squares estimation while preserving rigor and generality, yielding BLUE state estimates that incorporate observed data.
Problem
The Kalman filter addresses estimating the internal state of a discrete-time linear system, while many expositions omit detailed derivation steps.
Method
The note derives the discrete-time Kalman filter equations from least-squares estimation, using a concise treatment designed to minimize mathematical overhead while preserving rigor and generality.
Results
The derived Kalman filter equations yield the least-squares/BLUE estimate of the state at time n and account for observed data.
Takeaways & Limitations
The derivation provides a rigorous and general presentation of sequential Kalman filtering with limited mathematical overhead.
Abstract
from arXiv · showhide
In this lecture note, we present a concise and self-contained derivation of the discrete-time Kalman filter equations that requires only a basic understanding of least squares estimation. The treatment is designed to minimize mathematical overhead while preserving both rigor and generality.
SCOPE
The note builds the Kalman filter from least-squares estimation and standard linear-algebra identities, emphasizing a concise treatment that preserves rigor and generality.
- The presentation minimizes mathematical overhead while preserving rigor and generality.
- PREREQUISITES: The Gauss–Markov theorem identifies ordinary least squares as the best linear unbiased estimator under white noise.
- PREREQUISITES: For general noise covariance, the BLUE is obtained through generalized least squares, including a whitening step.
- PREREQUISITES: The Gauss–Markov estimator has the smallest error variance for each component and minimizes the sum of variances.
- PREREQUISITES: The derivation uses least-squares tools alongside the Woodbury matrix inversion identity and related matrix identities.
A + UCV
The Kalman filter estimates a discrete-time linear system’s current state from noisy observations and controls. The note formulates the estimation problem and develops iterative state estimation using prior estimates and covariances.
- KALMAN FILTER: PROBLEM STATEMENT: The Kalman filter estimates the internal state of a discrete-time linear dynamic system from noisy observations and control inputs.
- KALMAN FILTER: PROBLEM STATEMENT: The current state depends linearly on the previous state and possibly a control input, while measurements depend on the current state.
- KALMAN FILTER: PROBLEM STATEMENT: Measured data provide a partial and noisy state description that can improve the current-state estimate through data fusion.
- KALMAN FILTER: PROBLEM STATEMENT: The derivation assumes zero-mean process and observation noise, known system matrices and covariances, and a previous estimate with known covariance.
- SOLUTION: DERIVATION OF THE KALMAN EQUATIONS: The resulting equations provide the BLUE of the current state using both the prediction and observed data.
SOLUTION: DERIVATION OF THE KALMAN EQUATIONS
The derivation starts from a stacked linear model and least-squares estimation, then uses matrix identities to obtain the standard Kalman equations. The resulting formulation also extends to correlated process and measurement noise.
- Generalization: correlated process and measurement noise: The decorrelated formulation modifies the observations, measurement matrix, covariance, and Kalman gain to recover valid correlated-noise equations.
- The equations (15) give the BLUE of the state x′ while incorporating the observed data.
- Matrix identities transform the initial formulation into the standard Kalman filter form with only one m×m matrix inversion.
- The standard-form equations use the Kalman gain to rewrite the estimator in the usual prediction-and-update representation.
- Generalization: correlated process and measurement noise: For correlated process and measurement errors, a linear transformation decorrelates the noise terms before applying the least-squares derivation.
0 R −C⊤e Q−1C
The interpretation section presents the Kalman filter as prediction followed by measurement-based correction, with uncertainty-weighted estimation and several practical computational and modeling consequences.
- The Kalman filter is the least squares estimator of the state and becomes the Maximum Likelihood estimator for normally distributed noise.
- The estimate combines a model-based prediction with a correction driven by the observed measurement.
- Prediction and observation residuals are weighted according to their uncertainties, so greater uncertainty has less influence on the estimate.
- Without Gaussian assumptions, the variational formulation remains an alternative characterization under the stated second-order assumptions.
- Sequential Kalman filtering: When m = 1, the required m×m inversion reduces to scalar division, while block-diagonal R permits sequential block updates.
- At time k, the new estimate requires only the previous estimate and covariance, the current measurement, and the model matrices at time k.
- Tuning Q and R affects filter behavior: Q controls responsiveness to dynamics, whereas R governs sensitivity to measurement noise.
- Sequential Kalman filtering: Sequential Kalman filtering avoids matrix inversions for uncorrelated measurements by updating independent sensors one at a time.
WORKED NUMERICAL EXAMPLE (KALMAN FILTERING)
A two-dimensional constant-velocity robot example shows how sequential Kalman filtering combines position measurements with model predictions to estimate position and infer velocity. Measurement updates reduce covariance, reflecting increased confidence.
- Model setup: The example models a robot moving along a straight line with position and velocity as the state variables.It uses a constant-velocity model over sampling interval ∆t, with Bu = 0.
- Numerical settings: The example uses process-noise covariance Q = 0.01 I, measurement-noise covariance R = 0.04, and measurements z1 = 1.8 and z2 = 4.3.The initial estimate and covariance are specified at k = 0.
- Filtering steps: Sequential filtering repeats prediction, Kalman-gain and innovation computation, and data-fusion updates for each measurement.The no-data prediction is corrected using the observed measurement.
- Model setup: Only position is measured directly; velocity is inferred through the dynamics encoded in F.The scalar measurement provides no direct velocity observation.
- Interpretation: The filter combines model-based prediction with noisy measurements to improve both estimated position and inferred velocity.Because m = 1, the innovation covariance is scalar and the gain computation requires only scalar divisions.
- Interpretation: The decrease of Pk from P0 to P2 reflects increased confidence after incorporating measurements.The covariance reduction is the numerical example’s stated interpretation of the updates.
SEQUENCE OF OBSERVATIONS AND KALMAN: FILTERING AND SMOOTHING
The note extends a single least-squares/BLUE prediction–update step to sequences of observations. Iterating the equations gives filtering with past and current data, while future measurements support smoothing.
- Filtering: The previously derived least-squares/BLUE prediction–update equations and gain are applied iteratively over observations.The goal is to estimate the current state from z1:k.
- Filtering: Recursive application yields the optimal least-squares/BLUE estimate of xk given measurements z1:k.This is the filtering estimate based on observations available through time k.
- Smoothing: Future measurements z1:n with n > k can be incorporated to compute an optimal smoothed estimate of xk.Smoothing uses information unavailable to the filtered estimate at time k.
Model and estimation tasks
The discrete-time linear model supports two estimation tasks: filtering the final state from measurements through time n and smoothing earlier states using the full observation sequence. The note identifies classical Kalman filtering as the recursive solution to the first task.
- Model assumptions: The state-evolution equations are written as linear constraints involving F, xk−1, xk, and process noise wk.The model is specified for k = 1, 2, …, n.
- Model assumptions: The model assumes zero-mean, mutually independent noise terms and an unbiased prior (bx0, P0).Noise covariances are part of the stated model assumptions.
- Estimation tasks: Problem 1 estimates the final state xn using all measurements available at time n, denoted bxn|n.The available data are z1:n.
- Estimation tasks: Problem 2 estimates an intermediate state xk or the whole trajectory using all measurements through time n, denoted bxk|n.This is the smoothing task.
- Estimation tasks: Classical Kalman filtering solves Problem 1 recursively, while Problem 2 is addressed through smoothing.The note distinguishes filtering from estimation that uses future observations.
Batch (whole-sequence) least squares
Stacking the dynamics and measurements converts whole-sequence estimation into a block-structured least-squares system. Gaussian elimination yields a forward recursion equivalent to filtering and a backward recursion for smoothing.
- Batch formulation: Stacking the state and measurement equations produces a batch linear model y = Ax + n for the whole state sequence.The least-squares estimate satisfies a normal equation.
- Batch formulation: The resulting normal-equation system has block structure, including a block-tridiagonal matrix with blocks Dk.The interior diagonal blocks combine process, measurement, and transition terms.
- Forward recursion: Gaussian elimination avoids directly inverting the large matrix M and transforms the system through a forward recursion.The forward sweep determines the final filtered estimate bxn|n.
- Backward recursion: A backward back-substitution recursion recovers the remaining smoothed state estimates bxk|n.After the forward sweep, the system is upper block-bidiagonal.
- Filtering and smoothing: The forward recursion computes the least-squares estimate of the current state from past information and the current measurement.The backward recursion refines past-state estimates through smoothing.
Forward recursion (Kalman filtering)
The Kalman filter forward recursion is obtained by solving a structured least-squares problem, while backward substitution yields smoothing recursions for past states and covariances.
- Forward recursion (Kalman filtering): Kalman filtering implements the forward recursion used to solve the block-structured least-squares system.The derivation connects the standard filter equations with forward elimination of the associated linear system.
- Forward recursion (Kalman filtering): The filter output at time k is the filtered estimate x̄_k = x̂_k|k based only on measurements through time k.At time n, this estimate is the least-squares/BLUE estimate of x_n given z_1:n.
- Forward recursion (Kalman filtering): Backward substitution recovers the remaining state variables after the block Gaussian elimination and produces the smoothing recursion.Equation (34) is identified with the Rauch–Tung–Striebel smoother.
- Forward recursion (Kalman filtering): Smoothed covariances P_k|n are computed recursively backward from P_n|n = P_n and incorporate information from future measurements.Typically, P_k|n ≼ P_k, so smoothing reduces uncertainty at time k.
- Forward recursion (Kalman filtering): The backward recursion can refine past filtered state estimates using measurements collected after those states.This refinement applies to both state estimates and their covariances.
WORKED NUMERICAL EXAMPLE (CONTINUED): SMOOTHING
The numerical example illustrates smoothing as a backward refinement of earlier states using later measurements and the system dynamics.
- WORKED NUMERICAL EXAMPLE (CONTINUED): SMOOTHING: Smoothing improves estimates of past states x_0 and x_1 by exploiting all available measurements z_1 and z_2.The smoother recursion is applied to obtain smoothed states and covariances at k = 1 and k = 0.
- WORKED NUMERICAL EXAMPLE (CONTINUED): SMOOTHING: The future measurement z_2 refines x̂_1|1 and x̂_0|0 through the innovation at k = 2 propagated backward through the dynamics.The example highlights how later observations affect earlier estimates.
- WORKED NUMERICAL EXAMPLE (CONTINUED): SMOOTHING: The update is especially visible in the velocity component, which is inferred through the state model rather than measured directly.This provides a concrete illustration of how dynamics transmit future measurement information to an earlier unmeasured component.
WHAT WE HAVE LEARNED?
The note derives the Kalman filter from least squares and presents filtering and smoothing as consequences of a unified state-estimation formulation. It also emphasizes generality beyond Gaussian disturbances and compatibility with correlated errors.
- WHAT WE HAVE LEARNED?: The Kalman filter is fundamentally the least-squares estimator of a discrete-time linear system’s internal state.The formulation combines state prediction and measurements in a block-structured least-squares problem.
- WHAT WE HAVE LEARNED?: The derivation requires no assumption of Gaussian disturbances.Gaussian optimality appears as a special instance of the least-squares perspective.
- WHAT WE HAVE LEARNED?: Correlations between process and measurement errors are accommodated without structural changes to the equations.The note presents this as a generality of the same formulation.
- WHAT WE HAVE LEARNED?: When measurement-noise covariance is diagonal, sequential scalar updates avoid explicit matrix inverses and can improve numerical implementation.This is presented as an implementation option for the sequential formulation.
- WHAT WE HAVE LEARNED?: The least-squares viewpoint leads directly to both the Kalman filter and backward recursions for smoothing.This gives a unified interpretation of forward filtering and backward trajectory estimation.