Kalman Filtering

Kalman Filtering
Dan Simon
Innovatia Software
dan@innovatia.com
Copyright 1998–2001 Innovatia Software. All Rights Reserved.

Preliminaries

We humans have been filtering things for virtually our entire history. Water filtering is a simple example. We can filter impurities from water as simply as using our hands to skim dirt and leaves off the top of the water. Another example is filtering out noise from our surroundings. If we paid attention to all the little noises around us we would go crazy. We learn to ignore superfluous sounds (traffic, applicances, etc.) and focus on important sounds, like the voice of the person we're speaking with.

There are also many examples in engineering where filtering is desirable. Radio communications signals are often corrupted with noise. A good filtering algorithm can remove the noise from electromagnetic signals while still retaining the useful information. Another example is voltages. Many countries require in-home filtering of line voltages in order to power personal computers and peripherals. Without filtering, the power fluctuations would drastically shorten the useful lifespan of the devices.

Kalman filtering is a relatively recent (1960) development in filtering, although it has its roots as far back as Gauss (1795). Kalman filtering has been applied in areas as diverse as aerospace, marine navigation, nuclear power plant instrumentation, demographic modeling, manufactring, and many others. This paper uses a tutorial, example-based approach to explain Kalman filtering.

Mathematics

Consider the problem of estimating the variables of some system. In dynamic systems (that is, systems which vary with time) the system variables are often denoted by the term state variables. Assume that the system variables, represented by the vector x, are governed by the equation x_k+1 = Ax_k + w_k where w_kis random process noise, and the subscripts on the vectors represent the time step. For instance, if our dynamic system consists of a spacecraft which is accelerating with random bursts of gas from its Reaction Control System thrusters, the vector x might consist of position p and velocity v. Then the system equation would be

Equation 1:

System Equation

where a_k is the random, time-varying acceleration and T is the time between step k and step k+1. Now suppose we can measure the position p. Then our measurement at time k can be denoted z_k = p_k + v_k where v_k is random measurement noise.

The question which is addressed by the Kalman filter is this: Given our knowledge of the behavior of the system, and given our measurements, what is the best estimate of position and velocity? We know how the sytem behaves according to the system equation, and we have measurements of the position, so how can we determine the best estimate of the system variables? Surely we can do better than just take each measurement at its face value, especially if we suspect that we have a lot of measurement noise.

The Kalman filter is formulated as follows. Suppose we assume that the process noise w_k is white gaussian noise with a covariance matrix Q. Further assume that the measurement noise is white gaussian noise with a covariance matrix R, and that it is not correlated with the process noise. We might want to formulate an estimation algorithm such that the following statistical conditions hold:

§ The expected value of our estimate is equal to the expected value of the state. That is, "on average," our estimate of the state will equal the true state.

§ We want an estimation algorithim such that of all possible estimation algorithms, our algorithm minimizes the expected value of the square of the estimation error. That is, "on average," our algorithm gives the "smallest" possible estimation error.

It so happens that the Kalman filter is the estimation algorithm which satisfies these criteria. There are many alternative ways to formulate the Kalman filter equations. One of the formulations is given in the following equations.

Equations 2 - 5:

In the above equations, the superscript -1 indicates matrix inversion and the superscript T indicates matrix transposition. S is called the covariance of the innovation, K is called the gain matrix, and P is called the covariance of the prediction error.

Equation 5 is fairly intuitive. The first term used to derive the state estimate at time k+1 is just A times the state estimate at time k. This would be the state estimate if we didn't have a measurement. In other words, the state estimate propagates in time just like the state vector (see Equation 1). The second term in Equation 5 is called the corrector term, and it represents how much to correct the propagated estimated due to our measurement. Inspection of Equation 5 indicates that if the measurement noise is much greater than the process noise, K will be small (that is, we won't give much credence to the measurement); if the measurement nosie is much smaller than the process noise, K will be large (that is, we will give a lot of credence to the measurement).

Example

Let's look at an example. The system represented by Equation 1 was simulated on a computer with random bursts of acceleration which had a standard deviation of 0.5 feet/sec². The position was measured with an error of 10 feet (one standard deviation). The figure shows how well the Kalman Filter was able to estimate the position, in spite of the large measurement noise.

Kalman Filter Plot

The MATLAB program that I used to generate the above results is available for downloading. Don't worry if you don't know MATLAB - it's an easy-to-read language, almost like pseudo code. The parameters I used to generate the above results were alpha = 1, dt = 0.5, and duration = 30. If you use MATLAB to run the program you will get different results every time because of the random noise that is simulated, but the results will be similar to the above plot. Click here to download the MATLAB file.

Kalman filtering is a huge field whose depths we cannot hope to begin to plumb in such a brief paper as this. Thousands of papers and dozens of textbooks have been written on this subject since its inception in 1960. Some issues which complicate the application of the Kalman filter are as follows.

§ We have assumed that the system equation is linear (see Equation 1). What if the equation is nonlinear?

§ What if the measurement noise and process noise are not Gaussian, not white, and not independent of each other?

§ What if the statistics (for example, the covariance matrix) of the noise is not known?

§ What if, rather than estimating the state of a system as measurements are made, we already have all the measurements and we want to reconstruct a time history of the state? Can we do better than a Kalman filter? It would seem that we could since we have more information available (that is, we have future measurements) to estimate the state at a given time. This is called the smoothing problem.

§ Equations 2 - 5 are matrix equations, and as such can impose a large computational burden for high-dimensional systems. Is there a way to approximate the Kalman filter for large systems, reducing the computational load while still approaching the theoretical optimum of the Kalman filter?

§ What if the noise characteristics change with time? Can we somehow formulate a Kalman filter that adapts over time to changes in the noise characteristics?

§ What if, rather than desired to minimize the "average" estimation error, we desire to minimize the "worst case" estimation error? This is known as the minimax or H-infinity estimation problem. Innovatia Software has a white paper on this topic entitled Minimax Filtering.

References

Textbook - I’ve written a textbook that condenses everything I’ve learned about Kalman filtering over the past 20 years into 500 pages. The book web site is http://academic.csuohio.edu/simond/estimation. At that site you can download more Matlab code and read additional tutorial articles that I’ve written.

There have been dozens of other books written about Kalman filtering. Two texts that I've found particularly helpful in my study and application of Kalman filters are the following.

B. Anderson and J. Moore, "Optimal Filtering," Prentice-Hall, 1979.
Gelb, "Applied Optimal Estimation," The MIT Press, 1974.

The use of Kalman filters requires a lot of matrix algebra. Some helpful books on this topic are the following.

G. Golub and C. Van Loan, "Matrix Computations," The Johns Hopkins University Press, 1989.
R. Horn and C. Johnson, "Matrix Analysis," Cambridge University Press, 1985.

Some of the classic papers on Kalman filtering have been reprinted by the IEEE in the following useful volume.

H. Sorenson, "Kalman Filtering: Theory and Application," IEEE Press, 1985.

Peter D. Joseph's web page is a useful resource on the topic of Kalman filtering. Doctor Joseph has worked with Kalman filters since their inception in 1960, and coauthored perhaps the earliest text on the subject (1968). His web page includes lessons for the beginning, intermediate, and advanced student.

Here are some other nice web pages on the subject.

Home Credentials Publications White Papers

Last Revised: May 29, 2007