A New Approach to Linear Filtering and Prediction Problems

“A New Approach to Linear Filtering and Prediction Problems” is a paper by Rudolf E. Kalman, published in March 1960 in the Journal of Basic Engineering, a transactions journal of the American Society of Mechanical Engineers (ASME). It reformulated the classical problem of estimating a signal from noisy observations in terms of a dynamic system’s state and its transitions, and showed that the optimal estimate can be computed recursively by another linear dynamic system driven by the measurements. That recursive estimator is what is now called the Kalman filter.

Problem

By the late 1950s, optimal linear filtering and prediction meant Norbert Wiener’s theory. Wiener had shown that finding the best linear estimator of a signal in noise leads to the Wiener–Hopf integral equation, and he gave a solution by spectral factorization for stationary processes with rational spectra. Many extensions followed, for nonstationary processes, finite observation intervals, and sampled data, but each required its own derivation.

Kalman’s introduction lists four practical limitations of these methods. The optimal filter came as an impulse response, from which an actual filter is hard to build. Computing that impulse response numerically was laborious, ill suited to machines, and worse for larger problems. Generalizations such as growing-memory filters or nonstationary prediction each needed a new and often difficult derivation. And the derivations were opaque, hiding which assumptions mattered. Kalman’s aim was a single formulation that covered all of these cases and produced answers suited to machine computation.

Contribution

The paper’s central move is to describe random processes not by their correlation functions or spectra but as the output of a linear dynamic system driven by independent Gaussian noise, a representation the paper attributes to Bode and Shannon, combined with the state-transition method then being developed in control theory. The abstract claims three new results:

• the same formulation and solution handle stationary and nonstationary statistics, and filters with growing or infinite memory;
• the covariance of the optimal estimation error obeys a nonlinear difference (or differential) equation, and the optimal filter’s coefficients can be read off its solution;
• filtering is the dual of the noise-free optimal regulator problem of control theory, which Kalman had solved earlier.

Kalman states that only two of the paper’s theorems are original: the solution of the filtering problem (Theorem 3) and the duality theorem (Theorem 4). The remaining material reviews known results in a form suited to the new approach.

Method

State-space model. The paper works in discrete time, noting that this is not essential but keeps the mathematics elementary. Its main problem is stated for the model

$$\mathbf{x}(t+1) = \Phi(t+1; t)\, \mathbf{x}(t) + \mathbf{u}(t), \qquad \mathbf{y}(t) = M(t)\, \mathbf{x}(t),$$

where $\mathbf{x}(t)$ is the $n$-dimensional state, $\mathbf{u}(t)$ independent zero-mean Gaussian excitation, and $\mathbf{y}(t)$ a $p$-dimensional observation with $p \le n$. The matrices may vary with time. Unlike the modern formulation, the observation equation has no separate noise term: measurement noise is modeled as additional state components, as in the paper’s examples. The task is to estimate the state from observations $\mathbf{y}(t_0), \ldots, \mathbf{y}(t)$; filtering, prediction, smoothing, and reconstructing unmeasured state variables are special cases.

Orthogonal projection. The paper first shows that if the processes are Gaussian, or if the estimate is restricted to be linear and the loss is quadratic, the optimal estimate is the orthogonal projection of the unknown state onto the linear space spanned by the observations. In the Gaussian case it equals the conditional expectation and is optimal for a broad class of loss functions, so estimation becomes a geometric problem in a space of random variables.

Recursive solution. The key step is to split each new observation into the part predictable from past observations and the part orthogonal to them, which carries all of its new information (today called the innovation). Updating the projection with only this orthogonal part gives a recursion. In the paper it takes the form of a one-step predictor,

$$\mathbf{x}^*(t+1 \mid t) = \Phi^*(t+1; t)\, \mathbf{x}^*(t \mid t-1) + \Delta^*(t)\, \mathbf{y}(t), \qquad \Phi^*(t+1; t) = \Phi(t+1; t) - \Delta^*(t) M(t),$$

where the gain $\Delta^*(t)$ is computed from the error covariance. The paper stresses that the optimal estimator is itself a linear, possibly time-varying dynamic system whose state is the previous estimate and whose input is the latest observation; the estimation error obeys a linear system with the same transition matrix. The error covariance satisfies a nonlinear matrix difference equation, of the type now called a Riccati equation, that starts when observations begin and can be iterated numerically. Kalman describes it as loosely analogous to the Wiener–Hopf equation but much simpler to solve. The predict–update equations used today are an algebraic rearrangement of this recursion; see Kalman filter.

Duality. The paper then sets the filtering problem beside the deterministic problem of steering a linear system to minimize a quadratic cost. After reversing time and transposing the matrices, the recursions for the optimal regulator become those for the optimal filter, and vice versa.

Results

The paper’s results are theoretical. It gives two worked examples from nonstationary prediction in which the covariance recursion can be solved in closed form. The second is directly relevant to tracking: particles leave the origin with unknown constant velocities, the position of one is measured in correlated noise, and the filter estimates its position and velocity. For long observation times the result matches earlier solutions obtained by other methods. Numerical results for practical engineering problems were left to later publications.

Impact

The paper’s influence came from the combination of generality and computability. A filter defined by a finite-dimensional recursion, whose gains can be computed in advance or on the fly, fitted the digital computers then becoming available far better than an impulse response obtained by spectral factorization.

Aerospace adopted it quickly. According to McGee and Schmidt’s NASA account, Stanley Schmidt’s branch at the Ames Research Center was studying midcourse navigation for a circumlunar mission when Kalman visited in the autumn of 1960 and presented the paper. Because trajectory estimation is nonlinear, the group applied the filter to equations linearized about a nominal trajectory, and soon relinearized about the current estimate instead, which is what is now called the extended Kalman filter. Schmidt passed the results to Richard Battin at the MIT Instrumentation Laboratory, then working on Apollo guidance, and Kalman filtering became part of Apollo navigation and later a standard tool for aircraft and inertial navigation systems.

Through its duality with the regulator problem, the paper also helped make estimation and control two halves of one state-space theory of linear systems.

Limitations

• Linear, known models. The method assumes linear dynamics and observations and requires the transition matrices and noise statistics to be known. The paper explicitly sets aside how such a model is obtained from data.
• Gaussian or linear optimality. Optimality holds for Gaussian processes, or among linear estimators under quadratic loss. The paper itself notes that whether physical processes are Gaussian enough is hard to judge.
• Open theoretical questions. Kalman acknowledges that Theorem 3 does not settle the problem completely: the meaning of assumptions made in one step of the derivation, the convergence and stability of the covariance equation, and the stability of the filter are deferred to a future paper.
• Numerical behavior. The paper treats computation as straightforward. McGee and Schmidt describe how implementations on flight computers with short word lengths found the covariance recursion numerically delicate, which led to square-root formulations, first flight-tested in 1972.

What Came After

The continuous-time theory followed in 1961, in a paper by Kalman and Richard Bucy in the same journal. It derived a Riccati differential equation for the error covariance, which the authors called the variance equation, and used the duality principle to prove its properties. The continuous-time filter is often called the Kalman–Bucy filter. Extended, unscented, square-root, and information-form filters, smoothers, and particle filters followed.

Computer vision adopted the filter wherever a quantity has to be estimated consistently over time from noisy image measurements. In object tracking, a constant-velocity model much like the paper’s second example predicts where each object should appear in the next frame. The prediction narrows the search, its covariance gates detections for data association, and the update smooths the trajectory. SORT and many later multi-object tracking systems are built on this pattern. In camera motion estimation, the extended Kalman filter was the basis of early visual SLAM systems such as MonoSLAM, which estimated a single camera’s trajectory together with a sparse map of landmarks in real time. Filtering-based visual-inertial odometry continues the same approach.