Kalman Filter Easy Explanation

[Nayme Cutforth]

The whole thing was like a nightmare. Nothing made sense. The equations were composed of some ridiculously complex superscripted and subscripted variables combined with transposed matrices and untransposed some other stuff, which are totally unknowable to most of us.

And then, instead of aiming for the homework, I decided first fully concentrating on Kalman Filter itself. This article is the result of my couple of day's work and reflects the slow learning curves of a "mathematically challenged" person.

Also here, is the measurement value. Keep in mind that, we are not perfectly sure of these values. Otherwise, we won't be needing to do all these. And is called "Kalman Gain" (which is the key point of all these), and is the estimate of the signal on the previous state.

The only unknown component in this equation is the Kalman gain. Because, we have the measurement values, and we already have the previous estimated signal. You should calculate this Kalman Gain for each consequent state. This is not easy of course, but we have all the tools to do it.

The second equation tells that any measurement value (which we are not sure its accuracy) is a linear combination of the signal value and the measurement noise. They are both considered to be Gaussian.

The entities A, B and H are in general form matrices. But in most of our signal processing problems, we use models such that these entities are just numeric values. Also as an additional ease, while these values may change between states, most of the time, we can assume that they're constant.

If we are pretty sure that our system fits into this model (most of the systems do by the way), the only thing left is to estimate the mean and standard deviation of the noise functions Wk-1 and vk. We know that, in real life, no signal is pure Gaussian, but we may assume it with some approximation.

Here, is the prior estimate which in a way, means the rough estimate before the measurement update correction. And also is the prior error covariance. We use these prior values in our Measurement Update equations.

Now let's try to estimate a scalar random constant, such as a "voltage reading" from a source. So let's assume that it has a constant value of aV (volts), but of course we some noisy readings above and below a volts. And we assume that the standard deviation of the measurement noise is 0.1 V.

Here, I displayed the first 2 state iterations in detail, the others follow the same pattern. I've completed the other numerical values via a computer algorithm, which is the appropriate solution. If you try to write it as an algorithm, you'll discover that Kalman Filter is very easy to implement.

The chart here (right) shows that the Kalman Filter algorithm converges to the true voltage value. Here, I displayed the first 10 iterations and we clearly see the signs of convergence. In 50 or so iterations, it'll converge even better.

[1] Greg Welch, Gary Bishop, "An Introduction to the Kalman Filter", University of North Carolina at Chapel Hill Department of Computer Science, 2001
[2] M.S.Grewal, A.P. Andrews, "Kalman Filtering - Theory and Practice Using MATLAB", Wiley, 2001

Temporibus autem quibusdam et aut officiis debitis aut molestiae non recusandae rerum hic tenetur rerum necessitatibus saepe eveniet ut et voluptates repudiandae sint et molestiae non recusandae rerum hic tenetur.

Digital Signal Processing scholars deal with this same problem for decades, and there are lots of techniques developed for this problem. Kalman Filter is one of these techniques. And a very powerful one.

• First of all, it's not a filter at all, it's an estimator.
• It's a very, very important thing, it's not an overemphasize - believe me
• Being regarded as one of the greatest discoveries in 20th century.
• Hard to master it completely, but it's possible to play with it, with little mathematical background
• Very convenient to implement as a computer algorithm
• It's a recursive method, which means, for each instance, you use the previous output as an input.
• Yes, the equations are very complicated, and includes some mysterious matrices. But most of the time, you omit or ignore them - unless you carry through really complicated science.

Rudolf Kalman was born in Budapest, Hungary, and obtained his bachelor's degree in 1953 and master's degree in 1954 from MIT in electrical engineering. His doctorate in 1957 was from Columbia University.

Kalman is an electrical engineer by training, and is famous for his co-invention of the Kalman filter, a mathematical technique widely used in control systems and avionics to extract a signal from a series of incomplete and noisy measurements.

He had more success in presenting his ideas, however, while visiting Stanley F. Schmidt at the NASA Ames Research Center in 1960. This led to the use of Kalman Filters during the Apollo program.

Can I deploy Kalman Filter to all Digital Signal Processing problems?
I've seen lots of papers that use Kalman Filter for a variety of problems, such as noise filtering, sub-space signal analysis, feature extraction and so on. The bottom line is, you can use Kalman Filter with a quite approximation and clever modeling.

Where do we find these Time Update and Measurement Update equations? It seems that they suddenly appeared from nowhere.
You can derive it from the linear stochastic difference equation (the equations in STEP 1), by taking the partial derivative and setting them to zero (for minimizing the estimation error). Of course they're hard and time consuming.

Our robot also has a GPS sensor, which is accurate to about 10 meters, which is good, but it needs to know its location more precisely than 10 meters. There are lots of gullies and cliffs in these woods, and if the robot is wrong by more than a few feet, it could fall off a cliff. So GPS by itself is not good enough.

The GPS sensor tells us something about the state, but only indirectly, and with some uncertainty or inaccuracy. Our prediction tells us something about how the robot is moving, but only indirectly, and with some uncertainty or inaccuracy.

The Kalman filter assumes that both variables (postion and velocity, in our case) are random and Gaussian distributed. Each variable has a mean value \(\mu\), which is the center of the random distribution (and its most likely state), and a variance \(\sigma^2\), which is the uncertainty:

One thing that Kalman filters are great for is dealing with sensor noise. In other words, our sensors are at least somewhat unreliable, and every state in our original estimate might result in a range of sensor readings.

From each reading we observe, we might guess that our system was in a particular state. But because there is uncertainty, some states are more likely than others to have have produced the reading we saw:

This will allow you to model any linear system accurately. For nonlinear systems, we use the extended Kalman filter, which works by simply linearizing the predictions and measurements about their mean. (I may do a second write-up on the EKF in the future).

it seems its linear time dependent model. is it possible to introduce nonlinearity. what if the transformation is not linear. then how do you approximate the non linearity. every state represents the parametric form of a distribution. that means the actual state need to be sampled. is not it an expensive process?

You reduce the rank of H matrix, omitting row will not make Hx multiplication possible. If in above example only position is measured state u make H = [1 0; 0 0]. If both are measurable then u make H = [1 0; 0 1];

This is an excellent piece of pedagogy. Every step in the exposition seems natural and reasonable. I just chanced upon this post having the vaguest idea about Kalman filters but now I can pretty much derive it. The only thing I have to ask is whether the control matrix/vector must come from the second order terms of the taylor expansion or is that a pedagogical choice you made as an instance of external influence? Also, I guess in general your prediction matrices can come from a one-parameter group of diffeomorphisms.

I wish there were more posts like this. That explain how amazing and simple ideas are represented by scary symbols. Loved the approach. Can you please do one on Gibbs Sampling/Metropolis Hastings Algorithm as well?

After reading many times about Kalman filter and giving up on numerous occasions because of the complex probability mathematics, this article certainly keeps you interested till the end when you realize that you just understood the entire concept.

v.nice explanation. Actually I have something different problem if you can provide a solution to me. In my system, I have starting and end position of a robot. I need to find angle if robot needs to rotate and velocity of a robot. Can I get solution that what will be Transition matrix, x(k-1), b(k), u(k).
Thanks Baljit

I think that acceleration was considered an external influence because in real life applications acceleration is what the controller has (for lack of a better word) control of. In other words, acceleration and acceleration commands are how a controller influences a dynamic system.

I will be less pleasant for the rest of my comment, your article is misleading in the benefit versus effort required in developing an augmented model to implement the Kalman filter. By the time you invested the research and developing integrated models equations for errors of your sensors which is what the KF filter is about, not the the recursive algorithm principle presented here which is trivial by comparison.

Assume that every car is connected to internet. I am trying to predict the movement of bunch of cars, where they probably going in next ,say 15 min. you can assume like 4 regions A,B,C,D (5-10km of radius) which are close to each other. How can I make use of kalman filter to predict and say, so many number cars have moved from A to B.

c80f0f1006