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, and so on)

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 article uses a tutorial, example-based approach to

explain Kalman filtering.

Mathematics

Consider the problem of estimating the variables of a 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_{k} is 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

**(1)**

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:

S

_{k}= P_{k}+ R

(2)K

_{k}=

AP_{k}S_{k}^{-1}

(3)P

_{k+1}= AP_{k}A^{T}+ Q –

AP_{k}S_{k}^{-1}P_{k}A^{ T}(4)

_{ k+1}= A_{ k}+ K_{k}(z_{k+1}– A_{ k}(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). **Figure 1** shows how

well the Kalman Filter was able to estimate the position,

in spite of the large measurement noise.

**Figure 1:** Â The graph demonstrates the Kalman filter's ability to estimate position despite a large noise measurement

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 a = 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 to 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's Web site.

1998″2001 Innovatia Software. All Rights

Reserved.

**
**

## 0 comments on “Introduction to Kalman Filtering”