EQUATION-FREE DESCRIPTION The Kalman filter is a multiple-input, multiple-output digital filter that can optimally estimate, in real time, the states of a system based on its noisy outputs (see Figure 1). These states are all the variables needed to completely describe the system behavior as a function of time (such as position, velocity, voltage levels, and so forth). In fact, one can think of the multiple noisy outputs as a multidimensional signal plus noise, with the system states being the desired unknown signals. The Kalman filter then filters the noisy measurements to estimate the desired signals. The estimates are statistically optimal in the sense that they minimize the mean-square estimation error. This has been shown to be a very general criterion in that many other reasonable criteria (the mean of any monotonically increasing, symmetric error function such as the absolute value) would yield the same estimator. The Kalman filter was a dramatic improvement over its minimum mean square error predecessor, in-vented by Norbert Wiener in the 1940s, which was primarily confined to scalar signals in noise with stationary statistics. Figure 2 illustrates the Kalman filter algorithm itself. Because the state (or signal) is typically a vector of scalar random variables (rather than a single variable), the state uncertainty estimate is a variance-covariance matrix -- or simply, covariance matrix. Each diagonal term of the matrix is the variance of a scalar random variable -- a description of its uncertainty. The term is the variable's mean squared deviation from its mean, and its square root is its standard deviation. The matrix's off-diagonal terms are the covariances that describe any correlation between pairs of variables. The multiple measurements (at each time point) are also vectors that a recursive algorithm processes sequentially in time. This means that the algorithm iteratively repeats itself for each new measurement vector, using only values stored from the previous cycle. This procedure distinguishes itself from batch-processing algorithms, which must save all past measurements. Starting with an initial predicted state estimate (as shown in Figure 2) and its associated covariance obtained from past information, the filter calculates the weights to be used when combining this estimate with the first measurement vector to obtain an updated "best" estimate. If the measurement noise covariance is much smaller than that of the predicted state estimate, the measurement's weight will be high and the predicted state estimate's will be low. Also, the relative weighting between the scalar states will be a function of how "observable" they are in the measurement. Readily visible states in the measurement will receive the higher weights. Because the filter calculates an updated state estimate using the new measurement, the state estimate covariance must also be changed to reflect the information just added, resulting in a reduced uncertainty. The updated state estimates and their associated covariances form the Kalman filter outputs. Finally, to prepare for the next measurement vector, the filter must project the updated state estimate and its associated covariance to the next measurement time. The actual system state vector is assumed to change with time according to a deterministic linear transformation plus an independent random noise. Therefore, the predicted state estimate follows only the deterministic transformation, because the actual noise value is unknown. The covariance prediction ac-counts for both, because the random noise's uncertainty is known. Therefore, the prediction uncertainty will increase, as the state estimate prediction cannot account for the added random noise. This last step completes the Kalman filter's cycle. WHAT GAUSS SAID  If the astronomical observations and other quantities, on which the computation of orbits is based, were absolutely correct, the elements also, whether deduced from three or four observations, would be strictly accurate (so far indeed as the motion is supposed to take place exactly according to the laws of Kepler), and, therefore, if other observations were used, they might be confirmed, but not corrected. But since all our measurements and observations are nothing more than approximations to the truth, the same must be true of all calculations resting upon them, and the highest aim of all computations made concerning concrete phenomena must be to approximate, as nearly as practicable, to the truth. But this can be accomplished in no other way than by a suitable combination of more observations than the number absolutely requisite for the determination of the unknown quantities. This problem can only be properly undertaken when an approximate knowledge of the orbit has been already attained, which is afterwards to be corrected so as to satisfy all the observations in the most accurate manner possible. -- From Theory of the Motion of the Heavenly Bodies Moving about the Sun in Conic Sections, a translation by C.H. Davis of C.F. Gauss's 1809 Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Ambientium. Davis's 1857 translation was republished by Dover Publications, Inc., New York, in 1963.

One can see that as the measurement vectors are recursively processed, the state estimate's uncertainty should generally decrease (if all states are observable) because of the accumulated information from the measurements. However, because information is lost (or uncertainty increases) in the prediction step, the uncertainty will reach a steady state when the amount of uncertainty increase in the prediction step is balanced by the uncertainty decrease in the update step. If no random noise exists in the actual model when the state evolves to the next step, then the uncertainty will eventually approach zero. Because the state estimate uncertainty changes with time, so too will the weights. Generally speaking, the Kalman filter is a digital filter with time-varying gains. Interested readers should consult "The Mathe-matics of Kalman Filtering" sidebar for a summary of the algorithm.

If the state of a system is constant, the Kalman filter reduces to a sequential form of deterministic, classical least squares with a weight matrix equal to the inverse of the measurement noise covariance matrix. In other words, the Kalman filter is essentially a recursive solution of the least-squares problem. Carl Friedrich Gauss first solved the problem in 1795 and published his results in 1809 in his Theoria Motus, where he applied the least-squares method to finding the orbits of celestial bodies (see the "What Gauss Said" sidebar). All of Gauss's statements on the effectiveness of least squares in analyzing measurements apply equally well to the Kalman filter.

A SIMPLE EXAMPLE

A simple hypothetical example may help clarify the concepts in the preceding section. Consider the problem of determining the actual resistance of a nominal 100-ohm resistor by making repeated ohmmeter measurements and processing them in a Kalman filter.

First, one must determine the appropriate statistical models of the state and measurement processes so that the filter can compute the proper Kalman weights (or gains). Here, only one state variable -- the resistance, x -- is unknown but assumed to be constant. So the state process evolves with time as

x k+1 = xk . [1]

Note that no random noise corrupts the state process as it evolves with time. Now, the color code on a resistor indicates its precision, or tolerance, from which one can deduce -- assuming that the population of resistors has a Gaussian or normal histogram -- that the uncertainty (variance) of the 100-ohm value is, say, (2 ohm)2. So our best estimate of x, with no measurements, is x0/–= 100 with an uncertainty of P0/–= 4. Repeated ohmmeter measurements,

zk = xk + vk , [2]

directly yield the resistance value with some measurement noise, vk (measurement errors from turn-on to turn-on are assumed uncorrelated). The ohmmeter manufacturer indicates the measurement noise uncertainty to be Rk= (1 ohm)2 with an average value of zero about the true resistance.

Starting the Kalman filter at k = 0, with the initial estimate of 100 and uncertainty of 4, the weight for updating with the first measurement is

 P0/- 4 K0= ---------------- = --------------- P0/- + R0 4+1
, [3]

with the updated state estimate as

x0/0 = (1-K0)x0/- + K0z0

[4]

where x0/0 denotes the best estimate at time 0, based on the measurement at time 0. Note that the measurement receives a relatively high weight because it is much more precise (less uncertain) than the initial state estimate. The associated uncertainty or variance of the updated estimate is

P0/0 = (1 - K0)P0/- =
 1 4 --------- 4 = --- 4 + 1 5

. [5]

Also note that just one good measurement decreases the state estimate variance from 4 to 4/5. According to equation [1], the actual state projects identically to time 1, so the estimate projection and variance projection for the next measurement at time 1 is

 4 x 1/0 = x 0/0 ; P1/0 = P0/0 = --- 5
. [6]

Repeating the cycle over again, the new gain is

 P1/0 4/5 K1 = ------------- = ------ P1/0+R1 4/5+1
[7]

and the new update variance is

P1/1 = (1 - K1) P1/0 =

 1 4 4 ( --------- ) --- = --- 4/5 + 1 5 9
. [8]

Figure 3 represents a simulation of this process with the estimate converging toward the true value. The estimation uncertainty for this problem, which the Kalman filter provides, appears in Figure 4. One can see that the uncertainty will eventually converge to zero.

A New Set of Conditions. Let's now change the problem by assuming that the measurements are taken one year apart with the resistor placed in extreme environmental conditions so that the true resistance changes a small amount. The manufacturer indicates that the small change is independent from year to year, with an average of zero and a variance of 1/4 ohms2. Now the state process will evolve with time as

xk + 1 = xk + wk. [9]

where the random noise, wk, has a variance of Qk = 1/4. In the previous case, the variance prediction from time 0 to time 1 was constant as in equation [6]. Here, because of the random noise in equation [9], the variance prediction is

 4 1 P1/0 = P0/0 + Q0 = --- + --- = 1.05 5 4
. [10]

Now the gain and update variance calculations proceed on as in equations [7] and [8] but with larger values for the predicted variance. This will be repeated every cycle so that the measurement update will decrease the variance while the prediction step will increase the variance. Figure 5 illustrates this tendency. Eventually, the filter reaches a steady state when the variance increase in the prediction step matches the variance decrease in the measurement update step, with Pk+1/k = 0.65 and Pk/k = 0.4. The Qk represents a very important part of the Kalman filter model because it tells the filter how far back in time to weight the measurements. An incorrect value of this parameter may dramatically affect performance.

What Gauss Said

The Mathematics of Kalman Filtering