Innovation

1Estimating what cannot be seen directly

Consider the problem of following a moving object, an aircraft on a radar screen or a vehicle reported by its satellite navigation. What the observer wants to know is the object's true state: where it is, and how fast and in what direction it is moving. What the observer actually receives is a stream of measurements, and each measurement is imperfect. It is corrupted by noise, so no single reading is exact, and it is usually incomplete, reporting position but not velocity. The true state is never seen directly. It must be inferred.

A first instinct is to smooth the noise away by averaging. If the object were standing still, averaging many noisy readings of its position would indeed converge on the truth, because the errors, being random, would tend to cancel. The instinct fails because the object is not standing still. The quantity being measured is itself changing, and an average of all the readings taken so far is an average of positions the object has already left behind. It produces an estimate that trails the object, lagging further behind the faster the object moves. Averaging treats the state as a fixed unknown, and the state is not fixed.

What is needed is an estimate that respects two facts at once: that each measurement carries real information about the state, and that the state evolves between one measurement and the next. The Kalman filter achieves this by keeping a running estimate and, at every step, doing two things. It first predicts, using a model of how the state moves, where the state should have travelled to since the last measurement. It then corrects that prediction with the new measurement. The correction is not a wholesale replacement and not a simple average; it is a weighted compromise, and the weight depends on how much the filter trusts the prediction relative to the measurement. The rest of this document is an unfolding of that idea.

State

The set of quantities that describe the system completely enough to predict its future behaviour. For a moving object the state is usually its position together with its velocity, because position alone does not say where the object will be next. The state is what the filter estimates; it is hidden, and the measurements are partial, noisy glimpses of it.

2Representing uncertainty: the Gaussian

Before the filter can weigh a prediction against a measurement it must represent how uncertain each of them is. An estimate given as a single number, a bare position, carries no indication of how much to trust it. The Kalman filter therefore represents a belief about a quantity not as a number but as a distribution, and the distribution it uses is the Gaussian, the bell-shaped normal distribution. A Gaussian belief is described by exactly two quantities: a mean, which is the best single estimate, and a variance, which measures the spread and so the uncertainty. A narrow Gaussian is a confident belief; a wide one is a vague belief centred on the same value.

The Gaussian is chosen for three reasons. It is economical, capturing a belief in just a mean and a variance. It is also a natural model for measurement noise, because a disturbance that is the accumulation of many small independent effects tends toward a Gaussian regardless of the details, a fact made precise by the central limit theorem. The third reason is the one that matters most for the filter, and it concerns what happens when two Gaussian beliefs are combined.

Suppose two independent sources each provide a Gaussian belief about the same quantity, for instance a prediction of an object's position and a measurement of it. Combining them, in the sense of forming the belief consistent with both, corresponds to multiplying the two Gaussian functions together. The result of that multiplication is itself a Gaussian. Its mean is the average of the two input means weighted by their precisions, where precision is the reciprocal of variance, and its precision is the simple sum of the two input precisions. Two consequences follow. The combined estimate leans toward whichever input was more certain, because precision is the weight. And the combined belief is narrower than either input, because adding the precisions can only increase the total, which means combining two pieces of evidence always reduces uncertainty.

The figure above lets the two Gaussians be moved and widened, and draws their product. That product is the entire Kalman update in miniature. The remaining sections add the machinery needed to apply it to a system that moves and is observed through an imperfect sensor, but the act of folding a measurement into an estimate is, at its core, this multiplication of one Gaussian by another.

3A history of estimation: a literature review

The Kalman filter did not appear in isolation. It was the resolution of a problem that had been worked on for a century and a half, and each earlier method bequeathed to it a specific limitation that the filter was designed to remove. The account that follows is deliberately causal: in each case the question is which failure of an existing method prompted the next.

The oldest thread is the method of least squares, published by Legendre in 1805 [1] and given a probabilistic foundation by Gauss in 1809 [2], who connected it to the normal distribution and applied it to the determination of the orbits of celestial bodies from redundant, error-laden observations. Least squares is an estimator of fixed parameters: it finds the values of a set of unchanging unknowns that best fit a whole batch of measurements at once. For the problem of this document it has two shortcomings. It assumes the unknown is constant, whereas the state of a moving object is not, and it operates on the entire batch of data together, whereas a tracking system receives its data as an unending sequence and must produce an estimate continuously.

The problem of estimating a signal that changes in time, and is buried in noise, was taken up by Wiener, whose wartime work was published in 1949 [3], with Kolmogorov reaching related results independently. Wiener's filter was optimal, and it handled a time-varying signal, which least squares did not. Its limitations were nonetheless real. It assumed the signal and the noise were stationary, meaning that their statistical character did not itself change over time, so it did not apply to a system whose dynamics shift. It was expressed in the frequency domain and in terms of the entire past history of the signal, which sat awkwardly with a system that must estimate from a finite and growing record. And it did not extend gracefully to a system described by several interacting quantities.

The decisive step was taken by Kalman in 1960 [4], with the continuous-time counterpart given by Kalman and Bucy the following year [5]. Kalman recast the estimation problem in the language of state space: the system was described by a state vector evolving according to a difference equation, and the estimator was expressed in the time domain. Two properties followed that answered Wiener's limitations directly. The filter was recursive, needing only the previous estimate and the latest measurement rather than the whole history, which made it suited to a continuous stream of data and cheap enough to run as the data arrived. And it applied to systems that were time-varying and described by many coupled variables, not only to stationary scalar signals. The estimator was provably optimal for the class of problems it addressed, those that are linear and driven by Gaussian noise.

That class, linear and Gaussian, did not include every system of interest. A radar measures an object's range and bearing, which are nonlinear functions of its position in ordinary coordinates, and a filter built on linear models cannot accommodate such a measurement directly. The response was the extended Kalman filter, which handles a nonlinear model by linearising it: at each step the nonlinear relationships are replaced by their first-order Taylor approximations, taken about the current estimate, and the linear filter is then applied to the approximation. The extended filter found its most consequential early application in spacecraft navigation; Smith, Schmidt and McGee developed the approach for that purpose in 1962 [6], and a filter of this kind ran in the guidance computer of the Apollo programme. Its weakness is inherent in the linearisation. A first-order approximation is faithful only when the model is gently nonlinear across the range of the current uncertainty; for a strongly nonlinear system the approximation is poor, and the extended filter can produce an estimate that is not merely inaccurate but divergent.

The unscented Kalman filter, introduced by Julier and Uhlmann in 1997 [7], was created specifically because the extended filter's linearisation was inadequate for strongly nonlinear systems. Rather than approximate the model, the unscented filter approximates the distribution. It chooses a small, deterministic set of sample points whose mean and covariance match the current belief, passes each point through the exact nonlinear model, and recovers a mean and covariance from the transformed points. This captures the effect of the nonlinearity more accurately than a first-order expansion, and it does so without the differentiation that the extended filter requires.

Every filter named so far, the original, the extended and the unscented, represents its belief as a Gaussian. Some problems have beliefs that no Gaussian can represent, in particular beliefs that are multimodal, where the evidence leaves the state credibly in one of several separated places. For such problems Gordon, Salmond and Smith introduced the bootstrap particle filter in 1993 [8], which represents the belief by a population of weighted samples that are propagated through the model and periodically resampled. It abandons the Gaussian assumption entirely, at a substantially higher computational cost. The body of technique was consolidated for graduate study by Maybeck [9], organised around target tracking by Bar-Shalom and colleagues [10], and carried into the centre of modern robotics, where these filters underpin localisation and mapping, by Thrun, Burgard and Fox [11].

Two threads run through this history. The first is the movement from the batch estimation of fixed parameters toward the recursive estimation of a state that evolves in time. The second is a progressive loosening of assumptions: from stationary signals to time-varying ones, from linear models to nonlinear ones, and from Gaussian beliefs to beliefs of any shape. Each loosening was forced by a class of real systems on which the previous method failed.

4State and the model of motion

To estimate a moving object the filter must first decide what its state contains. Position by itself is an insufficient state, because knowing only where an object is now gives no basis for saying where it will be at the next measurement. The remedy is to include velocity in the state alongside position. The state is then a vector, and for an object moving in a plane it has four components: two of position and two of velocity. Velocity is itself never measured by the position sensor; it is a hidden component of the state that the filter nonetheless estimates, by observing how the position changes.

With the state chosen, the filter needs a model of how it evolves from one step to the next. This is the process model. The simplest useful model is constant velocity: over one time step the position advances by the velocity, and the velocity is assumed unchanged. Expressed in matrix form, this rule is the state transition that the prediction step applies. The model is deliberately an idealisation. A real object accelerates, turns and is buffeted, none of which constant velocity describes, and the discrepancy between the model and the world is accounted for by the process noise, a covariance added at each prediction to represent the uncertainty the model itself introduces.

The prediction step does two things at once. It moves the mean of the estimate forward according to the process model, and it enlarges the covariance. The covariance is enlarged for two compounding reasons: the existing uncertainty is carried forward and reshaped by the motion, and the process noise is added on top to reflect the model's own imperfection. The consequence is important. Each prediction made without a corresponding measurement increases the uncertainty, and a filter that only ever predicted would see its uncertainty grow without limit, its estimate becoming steadily more vague until it was worthless. Prediction alone degrades; the filter depends on measurements to arrest and reverse that growth.

The figure above carries out prediction repeatedly with no measurement supplied, and draws the position part of the covariance as an ellipse. The ellipse moves with the predicted estimate and visibly swells with every step, and it swells faster when the process noise is set higher. Its shape is informative: it tends to stretch along the direction of motion, because uncertainty in the velocity translates, step by step, into a growing uncertainty in position along the line of travel.

Covariance

The generalisation of variance to a state of several components. It records not only how uncertain each component is but how the uncertainties are correlated, so that, for example, an error in estimated velocity is understood to imply a related error in future position. For the two position components it can be drawn as an ellipse, whose size is the amount of uncertainty and whose orientation is the direction in which the uncertainty is largest.

5The measurement, and the innovation

A measurement is connected to the state by a measurement model, which describes what the sensor observes. A sensor rarely reports the state in full. A position sensor observes the two position components and is silent about velocity, and the measurement model expresses exactly that: it selects from the state the part the sensor sees. The reading the sensor returns is this selected part of the true state with measurement noise added, the noise having its own covariance that describes the sensor's precision.

When a measurement arrives, the filter is not empty-handed. It has just produced a prediction, and from that prediction it can say what the sensor ought to read if the prediction were correct, by passing the predicted state through the measurement model. The quantity that drives the filter is the difference between the measurement actually received and this predicted measurement. That difference is the innovation, also called the measurement residual, and it is the element after which this monograph is named.

The innovation deserves its central place because it is precisely the new information in the measurement. The part of the measurement that merely confirms the prediction tells the filter nothing it did not already believe; only the part that departs from the prediction can change the estimate. If the prediction were exactly right and the sensor were noiseless, the innovation would be zero and the measurement would leave the estimate untouched. The filter does not act on the measurement directly. It acts on the innovation, adjusting its estimate in the direction the innovation indicates.

The innovation carries an uncertainty of its own. It is the difference between a measurement, which is uncertain because of sensor noise, and a prediction, which is uncertain because of everything in the previous section, so its uncertainty is a combination of the two, the innovation covariance. This quantity is useful beyond the update itself. It says how large an innovation the filter should regard as normal, and a measurement whose innovation is far larger than the innovation covariance can account for is most likely an outlier, a spurious reading. Comparing each innovation against its covariance, which the figure above draws as a dashed ellipse around the prediction, is the standard way a filter screens measurements before trusting them, and it is the basis of the consistency checks discussed in the eighth section.

6The Kalman gain

The update step produces the corrected estimate by adding to the predicted estimate a multiple of the innovation. The multiplier is the Kalman gain, and the whole behaviour of the filter is concentrated in how that gain is set. If the gain were zero the filter would ignore its measurements and drift on prediction alone; if it placed the estimate entirely on the measurement the filter would discard its model and inherit the full noise of the sensor. The gain is the setting between those extremes.

The Kalman filter does not leave the gain to be chosen by hand. It computes the gain at every step from the uncertainties themselves. In the simplest scalar case the gain is the variance of the prediction divided by the sum of the variance of the prediction and the variance of the measurement. Read that formula in the two limits. When the measurement is very noisy, its variance dominates the denominator, the gain is close to zero, and the update barely moves the estimate from its prediction. When the measurement is very precise, its variance is small, the gain is close to one, and the update moves the estimate almost all the way to the measurement. The gain weighs the prediction against the measurement by their relative uncertainties, and it is the same precision-weighted compromise that the product of two Gaussians produced in the second section, now written for the filter.

The update step also revises the covariance, and it revises it downward. Folding a measurement into the estimate always reduces the uncertainty, because a measurement is evidence and evidence can only sharpen a belief. This is what counterbalances the growth of uncertainty during prediction described in the fourth section. The filter runs as a continual contest between the two: prediction inflates the covariance and the update deflates it, and over many steps the covariance settles to a steady level fixed by the ratio of the process noise to the measurement noise. Because the covariance changes at every step, the gain, which is computed from it, is recomputed at every step; the filter leans heavily on its measurements while its uncertainty is large and leans less on them once the uncertainty has settled.

The figure above shows the update for a single quantity, with the measurement noise adjustable. As the measurement is made noisier the gain falls, the updated estimate slides back toward the prediction, and the bar dividing trust between the two shifts accordingly. The result that the filter's computed gain is not merely reasonable but optimal, in the sense of producing the smallest possible expected squared error, holds whenever the system is linear and its noises are Gaussian, and it is the theorem at the centre of Kalman's 1960 paper [4].

A filter left to run on a system whose noise statistics do not change approaches a steady state. The covariance stops changing appreciably from one step to the next, settling at the value where the inflation contributed by prediction exactly cancels the deflation contributed by the update, and the gain, computed from the covariance, settles along with it. In that regime the filter applies very nearly a fixed gain at every step, and it becomes equivalent to a simpler constant-gain estimator, the form in which related trackers had been used before Kalman's formulation supplied a principled value for the gain. The interval before the steady state is reached is a transient during which the filter, started from a deliberately uncertain initial guess, draws hard on its first measurements to locate the state; the contraction of the covariance through exactly that transient is visible in the tracking figure of the next section.

7Tracking in two dimensions

The pieces now assemble into a working estimator. The Kalman filter runs as a loop with two steps in alternation. At each time step it predicts, advancing the estimate by the process model and enlarging the covariance, and it then updates, forming the innovation from the new measurement, computing the gain from the current covariance, correcting the estimate, and shrinking the covariance. The loop runs for as long as measurements arrive, carrying forward only the latest estimate and covariance from one step to the next.

The figure below runs that loop in full. The state has four components, position and velocity in each of two dimensions; the process model is constant velocity; the sensor reports position with Gaussian noise. The true path, the scattered noisy measurements and the filter's estimate are drawn together, and the estimate can be seen to follow the truth through the scatter. The estimate is markedly smoother than the measurements, and the reason is structural: the filter does not chase each measurement, it blends each one with a prediction grounded in the whole history of motion, so the random excursions of individual readings are damped.

The figure exposes the two noise parameters, and adjusting them shows that they are the filter's tuning. Their ratio sets its character. A small process noise tells the filter to trust its motion model, which yields a very smooth estimate that lags whenever the object manoeuvres in a way the model does not anticipate. A large process noise tells the filter to distrust its model, which lets the estimate respond quickly to manoeuvres at the cost of admitting more of the measurement noise. In practice the process and measurement noises are seldom known exactly and must be tuned against recorded data, and the choice is the central practical skill in applying the filter. The figure also reports the average error of the estimate and of the raw measurements, and a well-tuned filter keeps the former below the latter, which is the concrete sense in which the filtering has done useful work.

8Sensor fusion and the filter's limits

Because the filter combines information by weighting it according to precision, it extends without modification to more than one sensor. Two sensors observing the same object, of different accuracies, are incorporated by applying the update step for each in turn, and each contributes in proportion to its precision. The more accurate sensor influences the estimate more, while the less accurate one still improves it rather than being discarded. This is sensor fusion, and a common instance of it pairs a sensor that is frequent but coarse with one that is accurate but infrequent, the filter carrying the estimate forward on the frequent sensor and sharply correcting it whenever the accurate one reports.

The mechanics of fusion follow directly from the update step. Each sensor carries its own measurement model, selecting and transforming the part of the state it observes, and its own noise covariance. When a reading arrives from any sensor, the filter forms the innovation against its current prediction, computes a gain from that sensor's noise, and applies the update; a reading from a second sensor is then handled in the same way against the already corrected estimate. Sensors that report at different rates need no special handling, because the prediction step simply advances the estimate to the time of whichever measurement comes next. The filter is, in this sense, indifferent to where a measurement originates, and asks of each one only how precise it is and what part of the state it concerns.

The filter's optimality is conditional, and an honest account must say on what it depends. The first condition is that the process model matches the real motion. When it does not, when an object manoeuvres sharply while the filter assumes constant velocity, the predictions are systematically wrong, the estimate lags, and if the process noise has been set too low the filter cannot respond quickly enough to recover. This kind of failure is detectable. A correctly tuned filter produces a sequence of innovations that is small, centred on zero and free of correlation from one step to the next; innovations that are persistently large, or that drift, are the signature of a process model that does not fit, which is why monitoring the innovation sequence is a standard diagnostic.

The second condition is linearity. The filter developed here assumes that the process and measurement models are linear, and many real measurement models, such as the range and bearing returned by a radar, are not. The extended and unscented filters described in the literature review exist precisely to remove this condition, the first by linearising the models and the second by propagating sample points through them. The third condition is that the belief is well described by a Gaussian. When the true belief is multimodal, leaving the state credibly in one of several distinct places, no Gaussian filter can represent it, and the particle filter is the recourse. The figures in this document use the linear Gaussian filter throughout, and because the synthetic data they run on is itself generated by a linear, constant-velocity process with Gaussian noise, the filter is not an approximation there but the exact optimal estimator for the data.

9Conclusion

The Kalman filter answers a question that arises wherever a system is watched through imperfect instruments: what is the true state, given a history of noisy and incomplete measurements of it. This document has built the answer one piece at a time. The state is the set of quantities, position and velocity together, that describe the system well enough to predict it. A belief about the state is represented as a Gaussian, a mean paired with a covariance. The prediction step carries the belief forward through the process model and inflates its covariance. The measurement enters through the innovation, the residual between the measurement and what the prediction expected. The Kalman gain weighs prediction against measurement by their relative uncertainties, and the update folds the measurement in and contracts the covariance. Run as a loop, predicting and then updating, the filter tracks a state it never observes directly.

The literature review placed that construction in its history and argued that it was the removal, one limitation at a time, of the shortcomings of earlier estimators. Least squares estimated fixed parameters from a batch; Wiener's filter handled a changing signal but required it to be stationary and its whole history to be in hand; Kalman's filter made the estimate recursive and admitted time-varying, multivariable systems; the extended and unscented filters admitted nonlinear ones; the particle filter admitted beliefs of any shape. The two long movements of the subject, from batch toward recursive estimation and from restrictive assumptions toward general ones, are legible in every step.

A reader who has followed the argument is prepared for what lies beyond it, because the remaining topics are extensions of the parts built here. The extended and unscented filters generalise the prediction and update to nonlinear models; the particle filter replaces the Gaussian belief with a population of samples; smoothing revisits past estimates in the light of later data; and the tuning and consistency testing of a filter, through its innovation sequence, is the discipline that makes it work on real data. Each is an answer to a definite limitation of what this document has described, which is the same pattern the literature review traced. The quantity at the centre of the method, the residual on which every correction is built, is the innovation that gives this monograph its name.