How Kalman Filters Work | Hacker News Reader

How Kalman Filters Work

anuncommonlab.com

377 pointsslackpad29 comments

I spent quite a bit of time working through the Kalman filter content in Sebastian Thrun's book "Probabilistic Robotics"[1] a while back. I ended up making some notes [2] of the process that might be of interest to others if you're trying to get a grasp of everything that's going on with that process. One other person on the Internet that I know of thought they were useful, so I'll post the link here. This was part of a project I was working on to build a K-8 robotics curriculum (no, not teaching the kids Kalman filters, but I wanted to know how it all worked before starting to make a curriculum). The book is really good if you're wanting to make robots that can navigate uncertain environments.

Edit: I wish I'd had access to this article when I was going through that process. This is really well done.

1. http://amzn.com/0262201623

2. https://github.com/aethertap/probabilistic-robotics

There is also a class at Stanford that builds up all the theory of the Kalman filter, starting with elementary probability [1]. The slides are all posted, and while they wouldn't be great to learn the material from, they're an excellent reference (and go into more depth on multivariate Gaussians and estimation theory than Probabilistic Robotics).

1. http://engr207b.stanford.edu/

Weird that Sebastian Thrun would come up again - he's on the front page stepping down as Udacity CEO right now [1], too, and I'd never heard of the guy before.

1 https://news.ycombinator.com/item?id=11562468

That's because he has had tremendous impacts on computer science and robotics for many years now as a pioneering professor at CMU and Stanford. He was a leading force in the DARPA grand challenge which showcased self driving car technologies long before it was cool. He led the self driving car project at Google-X, developed street view, and cofounded Udacity.

It's not weird; the guy is brilliant and has had many large impacts to the community as a whole.

In that case it's weird that I wasn't familiar with the name.

I suggest building one with any Matrix libraries you have available. It is a great exercise (if sometimes frustrating). There is nothing like covariance matrices blowing up in your face to teach you the machinations of the Kalman Filter.

Also a great exercise in scientific computing.

I was wondering who are you and why are you doing this? Are you doing this profit? Doesn't seem like it. You seem to be a great guy! Keep up the good work. World needs more people like you.

Thanks for the kind words! I'm not doing it for profit, just the desire to share something that took an unexpected level of effort for me to sort out.

Eventually I plan to open source the robotics curriculum that spawned this project, along with some other stuff related to starting a new school (something I'm working on with a team that was originally inspired by the XQ Superschool competition [1]). I want to run it through its paces with some real children first to make sure it's not completely off base though.

1. http://xqsuperschool.org/

The best presentation that I've ever seen on what a Kalman filter really is comes from a SIAM Review article, "A Fresh Look at the Kalman Filter" by Jeffrey Humpherys, Preston Redd, and Jeremy West

http://epubs.siam.org/doi/abs/10.1137/100799666

It sets up the discrete-time linear system and then uses a minimization principle to show what's going on. I can highly recommend it especially for people coming to Kalman filters from a math or optimization background.

Yes! If you put the process covariance aside, then Kalman filtering really just is a linear least squares problem solved incrementally, using Woodbury formula to solve the normal equations efficiently.

Now I know how my wife feels when she asks what I'm up to...

I'd like to add Roger Labbe's free book "Kalman and Bayesian Filters in Python" to the mix. Along with Thrun (which he cited to point me at), this is the resource that finally drove it home for me.

https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...

For people wondering about application, one of the popular recent uses is for sensor fusion in virtual reality.

More on application: Historically, KFs are used extensively for sensor fusion in the aviation industry. Aircraft (and missiles) use internal gyroscopes(INUs) for navigation in association with GPS. The INUs are prone to drifting and corrected with Kalman Filter estimated real time drift errors. These error rates are computed while GPS information is available and continue to be corrected in the case of GPS loss.

For people familiar with Gaussian Processes, it may help to think of Kalman filters as a special case of GPs where you can construct the inverse of the covariance matrix directly, and this inverse has a tridiagonal structure.

Thus, a really efficient Bayesian regression algorithm.

What's even more interesting is that there is some experimental evidence to suggest that the human brain uses Kalman filters for certain things. I think this was one of the papers about it: http://papers.nips.cc/paper/3665-a-neural-implementation-of-...

I find it odd that nowhere in the 3-part series is discussed the relationship between kalman filters and hidden markov models.

Thanks! I've not yet dived deep into kalman filters but only done hhm a bit and therefore hoped to get exactly this relationship uncovered.

Can you summarize or link to this relationship :) ?

In both models, there's an unobserved state that changes over time according to relatively simple rules, and you get indirect information about that state every so often.

In Kalman filters, you assume the unobserved state is Gaussian-ish and it moves continuously according to linear-ish dynamics (depending on which flavor of Kalman filter is being used).

In HMMs, you assume the hidden state is one of a few classes, and the movement among these states uses a discrete Markov chain.

In my experience, the algorithms are often pretty different for these two cases, but the underlying idea is very similar.

Another nice explanation, a bit more visual.

http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures...

What many don't know about Kalman Filters (and took me a while to realize as well) is that it's just recursive least squares.

It is just formulated a bit differently such that incremental update complexity depends of the dimensionality of the observation, not the dimensionality of the estimated state. Depending on the dimensions this can be a lot more efficient.

Best breakdown from a conceptual as well as mathematically precise description I have ever read.

Nice writeup. I use these filters quite often (especially the particle filter). Very powerful tools.

In what context do you use them?

They're used quite extensively in GPS/positioning.

Basically situations where you have a few data sources for the same thing, all with their own margins of error, update rate, etc. And you want to combine them to get one better data point. Eg in robotics, you can put together GPS, vision (e.g. from visual markers or perceived movement) and wheel encoder (how many times did the wheel spin, where do I think I am based on that) data to get one much more accurate location point.

Robotics in different contexts. I've used two different styles of Kalman filter for cleaning up data from computer vision based pose/velocity estimation. I also used a particle filter as a way of tracking humans in thermal images from a camera on a UAV.

https://www.youtube.com/watch?v=xMf-XW8vv0k

Adaptive Filter Theory by Simon Haykin is the single best engineering book I used. http://www.amazon.com/Adaptive-Filter-Theory-Simon-Haykin/dp... Covers Kalman filters in great detail. Did anyone else us it?

Awesome to see some Kalman filters! Takes me back to my undergrad :-)

Reply on news.ycombinator.com