How a Kalman filter works, in pictures(bzarg.com)
bzarg.com
How a Kalman filter works, in pictures
https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/
80 comments
Michel van Biezen has an excellent video series on Kalman filters:
https://www.youtube.com/watch?v=CaCcOwJPytQ
He walks you though all the way from the rationale, to a simple algebraic example, to the full blown Linear Algebraic Matrix solution. It's really worth watching even just the first couple videos to get a deeper understanding of this very useful technique.
https://www.youtube.com/watch?v=CaCcOwJPytQ
He walks you though all the way from the rationale, to a simple algebraic example, to the full blown Linear Algebraic Matrix solution. It's really worth watching even just the first couple videos to get a deeper understanding of this very useful technique.
> The Kalman Filter (video 1 of 55)
That seems... excessive.
That seems... excessive.
Average length of these videos are 5 minutes.
it's not 55 videos (dunno if he forgot to upload them or misnumbered them...). Also most of it (I'd say 70%) is him doing matrix multiplications on a whiteboard. Which is excellent if you need a refresher in linear algebra (or just suck at it ;)), otherwise you can skip a lot of the content. That aside, he does an excellent job explaining it.
The best exercise I had in our sensing & estimation class was to derive the Kalman filter from 'scratch'. It's actually just the series of steps used to perform a minimization of a convex cost function, where the cost function is the inverse likelihood of the measurements given the data.
Someone once joked that all of sensing and estimation (and path planning and optimal control) is just applied convex minimization.
Someone once joked that all of sensing and estimation (and path planning and optimal control) is just applied convex minimization.
Nice. I wrote up another possible derivation here https://ngr.yt/blog/kalman/ in case anyone is interested.
Where KFs finally clicked for me was in deriving the recursive form of good old fashioned linear regression. You can do linear regression a data point at a time, or a batch at a time, and while I can't remember if it works out to exactly the same thing (because of the recursive state), it works out to essentially the same. Dynamic bayesian networks are a superclass of KFs and they're a great thing to have in your tool kit if you work with data.
This article is fantastic.
For those who have some familiarity with Python, I found this to be a great resource for Kalman Filtering: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
For those who have some familiarity with Python, I found this to be a great resource for Kalman Filtering: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Seconded! I worked through this partway and appreciate some of the intuitions they build up.
It seems to me that there is no shortcuts to grokking the KF than going through simpler filters/Bayesian update algorithms.
Another resource I personally enjoy is Student Dave's lectures on YouTube. He's really entertaining and shows both pen-and-paper examples and Matlab simulations.
It seems to me that there is no shortcuts to grokking the KF than going through simpler filters/Bayesian update algorithms.
Another resource I personally enjoy is Student Dave's lectures on YouTube. He's really entertaining and shows both pen-and-paper examples and Matlab simulations.
Excellent, thank you! The article did a good job telling me what a Kalman filter looks like in math, but I really wanted one that told me what it looks like in code.
The most thorough explanation of Kalman filter as recursive least square coupled with linear state-space models is
"Linear Estimation" by Thomas Kailath, Ali H. Sayed, Babak Hassibi.
It covers robust numerical algorithms such as square-root Kalman filter.
Unfortunately, it is a big book and reading it is going to be a big time investment, but I believe it will be a worthwhile investment. It develops in depth various linear algebra concepts and demonstrates profound application to linear least square. This book is what people mean when they say learn from masters.
It is also the only technical book I have read that aptly quotes Shakespeare: "Age cannot whither her, nor custom stale her infinite variety."
It is also the only technical book I have read that aptly quotes Shakespeare: "Age cannot whither her, nor custom stale her infinite variety."
thx for the suggestion.
I appreciate how this post gets resubmitted every couple of years. It's been a go-to bookmark for ages now and really does help give some visual intuition for what's happening.
Where do you use it?
The way I've always seen a Kalman filter is as a recursive least squares fitter, but instead of being run on the same input until convergence, it is run one step on every new sample of ever-changing inputs, in effect leading to a smoothing fitter.
For some reason I rarely see it being described as such.
For some reason I rarely see it being described as such.
What's the "recursive" part? It's like the difference between IIR and FIR?
That is an astute connection. The "recursive" part is that you do not need to keep all the history of observations and actions (often denoted y and u. in control theory). You can summarize the past with sufficient statistics (the mean and the variance for linear quadratic gaussian (LQG) problems).
You could imagine keeping all of the data and fitting a model to that. For LQG problems, you can use dynamic programming [1] to solve the problem faster.
You could alternatively imagine keeping a finite window of data and fitting a model to that. That filter would have a finite impulse response.
[1] https://en.wikipedia.org/wiki/Dynamic_programming btw that term kind of means two things, and this is a situation in which the two meanings overlap.
You could imagine keeping all of the data and fitting a model to that. For LQG problems, you can use dynamic programming [1] to solve the problem faster.
You could alternatively imagine keeping a finite window of data and fitting a model to that. That filter would have a finite impulse response.
[1] https://en.wikipedia.org/wiki/Dynamic_programming btw that term kind of means two things, and this is a situation in which the two meanings overlap.
We also use it for fitting charged particle tracks in high energy physics experiments.
Here, we’re iteratively incorporating measurements along the trajectory, finally arriving at basically a least squares fit result, after a backward smoothing pass.
Here, we’re iteratively incorporating measurements along the trajectory, finally arriving at basically a least squares fit result, after a backward smoothing pass.
somewhat related fft/data smoothing:
https://dawn.cs.stanford.edu/2017/08/07/asap/
made a recent demo vs a moving avg: https://leeoniya.github.io/uPlot/demos/data-smoothing.html
moving avg takes a bunch of samples to converge, while ASAP does it much faster, which seems to also be a key property of these Kalman filters as well?
https://dawn.cs.stanford.edu/2017/08/07/asap/
made a recent demo vs a moving avg: https://leeoniya.github.io/uPlot/demos/data-smoothing.html
moving avg takes a bunch of samples to converge, while ASAP does it much faster, which seems to also be a key property of these Kalman filters as well?
Although not a Kalman filter, the "three cornered hat" thing sailors do to apply three distinct points of measurement to some reference and then using the triangle that forms as a limit to uncertainty is not dissimilar in intent and outcome.
Perhaps the main quality a kalman filter brings is the repeated application. If you imagine 20 sailors all doing the three cornered hat and another 20 doing a log line to assess speed, and a third doing some kind of ded reckoning.. a Kalman filter is what you apply over all of them to reduce it to your best most certain position and speed and heading?
I do wonder if false positives can drive in reverse to higher levels of uncertainty, not refinement. So a spurious echo on radar might contradict two other inputs.
The two overlapping coloured Gaussian clouds and the "aha" moment in the common region was good. It reinforces the idea of how two different measurements with their own uncertainty can combine to give a better certainty of the region of interest.
Were these not also used in analogue circuits to do feedback for missile tracking from radar/telemetry?
I struggle with algebras and formulae. The graphics help imbue some understanding.
Perhaps the main quality a kalman filter brings is the repeated application. If you imagine 20 sailors all doing the three cornered hat and another 20 doing a log line to assess speed, and a third doing some kind of ded reckoning.. a Kalman filter is what you apply over all of them to reduce it to your best most certain position and speed and heading?
I do wonder if false positives can drive in reverse to higher levels of uncertainty, not refinement. So a spurious echo on radar might contradict two other inputs.
The two overlapping coloured Gaussian clouds and the "aha" moment in the common region was good. It reinforces the idea of how two different measurements with their own uncertainty can combine to give a better certainty of the region of interest.
Were these not also used in analogue circuits to do feedback for missile tracking from radar/telemetry?
I struggle with algebras and formulae. The graphics help imbue some understanding.
When I started working with aviation people early in my career, learning that radar only has a fairly good guess of where you are was pretty amazing.
Unfortunately for me, the intuitive part of Kalman filters is easy, but I don't have nearly the kind of grasp of Linear algebra I would need to implement one (I think).
Are there drop in, batteries included, ready to go kalman filter implementations/frameworks for common microcontrollers like arduino and raspberry pi 2040? Or is it infeasible to implement them in limited setups?
Are there drop in, batteries included, ready to go kalman filter implementations/frameworks for common microcontrollers like arduino and raspberry pi 2040? Or is it infeasible to implement them in limited setups?
If you're willing to just believe that there's a derivation that it works, actually implementing a kalman filter is pretty straightforward. The proof is a pain, but you don't have to be able to derive it to use it.
You might be interested in TinyEKF: https://github.com/simondlevy/TinyEKF
Totally feasible in microcontroller for small ones and modest update rates, yes. I have worked with robots that had them implemented in slow 8-bit microcontrollers. (I did not do the KF, though).
> Unfortunately for me, the intuitive part of Kalman filters is easy, but I don't have nearly the kind of grasp of Linear algebra I would need to implement one (I think).
This is me, anyone got a good linear algebra resource to recommend? Ideally one that addresses 'I took linear algebra ages ago in uni but it didn't really stick'.
This is me, anyone got a good linear algebra resource to recommend? Ideally one that addresses 'I took linear algebra ages ago in uni but it didn't really stick'.
I really like "Linear Algebra and Its Applications" by Gilbert Strang. It is not a textbook, the style is conversational, and he really tries to help you learn. It is one of rare math books that includes reason, context, application, and history without sacrificing rigor. The book also focuses on numerical algorithms aspects more than some popular textbooks, which may be helpful to understanding Kalman filter.
Thanks for the suggestion!
I believe ROS (Robotic operating system) has good implementations of state estimation algorithms. If you are worried about memory footprint, then Durbin and Koopman ("Time Series Analysis by State Space Methods") has a scalar version of squared-root Kalman filter (it ingests one number at a time rather a whole vector at a time). You may have to implement it yourself though.
I think you still need a good grasp of linear algebra and difference equations to identify state variables and correctly set up the “model” or “plant” matrix, this is specific to the system so it can’t be provided by the framework. If you can do this, the rest of the Kalman filter is straightforward and can easily be done in numpy etc.
The computational requirements are very modest. The magic is in the math. I'm not sure if it counts as "batteries included" but I wrote a Kalman filter implementation in "no-std" (no standard library) rust called adskalman [1]. This means it can run on very modest bare metal targets with no operating system. Of course, it can also run on targets where the standard library is available and the examples [2] make use of this to do nice things like print the results which can be piped to a file and plotted. The core runs fine on embedded targets, and we use this with arm microcontrollers, but it should work on just about anything. Feedback is welcome.
[1] https://crates.io/crates/adskalman [2] https://github.com/strawlab/adskalman-rs/blob/main/examples/...
[1] https://crates.io/crates/adskalman [2] https://github.com/strawlab/adskalman-rs/blob/main/examples/...
I remember this blog post from ~3 years ago when I had to write my MPhil thesis :) thanks for this, it really helped me understand it!
Welford's online algorithm for computing weighted mean is essentially just Kalman filtering: Weights are the inverse of measurement covariance, i.e. the information, the initial state is the first measurement, state transition and observation model are 1x1 identity matrices.
I've been considering writing up something for extended kalman filters like this. Kalman filters are great but in my experience extremely limited without the non-linear extensions which make them useful in a much wider variety of problems.
Awesome article. Maths education needs way more visualisation in it like this.
I first found out about Kalman Filters when looking up how large ships use software to remain stationary in the same geographical location even whilst surrounded by crazy waves.
I first found out about Kalman Filters when looking up how large ships use software to remain stationary in the same geographical location even whilst surrounded by crazy waves.
As a matter of principle, I feel like this excellent article should contain contain the term "Bayesian update."
down atm. https://archive.md/cLjvZ
A related and much more powerful predictor in a noisy environment is the Particle Filter, which uses a mechanism that is particularly appealing to me as a programmer…
Author here. The particle filter has its own strengths and drawbacks. It makes more sense to use a particle filter in situations where the state search space is highly nonlocal and/or nonlinear, for example locating a drone on a map by matching radar features to topography.
If the process is linear and the estimation error is Gaussian (or approximately so in practice), the Kalman filter is known to be the optimal algorithm, and the particle filter would not only perform worse, but be more expensive to implement.
If the process is linear and the estimation error is Gaussian (or approximately so in practice), the Kalman filter is known to be the optimal algorithm, and the particle filter would not only perform worse, but be more expensive to implement.
> more expensive to implement
Theoretically this is precisely true, but in practice the difference is negligible for many models given the incredible computer power of modern hardware. A particle filter with a million points is trivial to model on even a mobile phone GPU with milliwatt levels of power draw.
Even "simple" cases like blending GPS data with other sensors could potentially benefit from a particle filter model. For example, an advanced particle filter could model the GPS signal echoing off buildings, which might result in multiple local maxima in the location probability space.
Most (all?) current systems simply throw away the other peaks in the GPS signal and feed in only the one with the "highest likelyhood".
Similarly, wheel tick counters typically use one wheel as an input. A particle filter could take all four wheels and be able to model disagreements in a robust way.
Particle filters are also better where the probabilities are not Gaussian. E.g.: measurements that are strictly positive often don't have Gaussian PDFs.
Theoretically this is precisely true, but in practice the difference is negligible for many models given the incredible computer power of modern hardware. A particle filter with a million points is trivial to model on even a mobile phone GPU with milliwatt levels of power draw.
Even "simple" cases like blending GPS data with other sensors could potentially benefit from a particle filter model. For example, an advanced particle filter could model the GPS signal echoing off buildings, which might result in multiple local maxima in the location probability space.
Most (all?) current systems simply throw away the other peaks in the GPS signal and feed in only the one with the "highest likelyhood".
Similarly, wheel tick counters typically use one wheel as an input. A particle filter could take all four wheels and be able to model disagreements in a robust way.
Particle filters are also better where the probabilities are not Gaussian. E.g.: measurements that are strictly positive often don't have Gaussian PDFs.
> but in practice the difference is negligible [...] A particle filter with a million points is trivial
This will be O(millions * state_size) of flops per frame. A Kalman filter of the same state size will have the expense of a matrix invert, which will be O(state_size^3). So for a state size of, say, 12 floats, the Kalman will be about O(2000)-ish flops. A particle filter with "millions of points" modeling the same system will be O(state_size * millions * flops_per_state_update) which could be literally billions of flops, a six order of magnitude difference.
While there are absolutely applications where the particle filter is a more appropriate choice, it's just false to say that the performance difference is negligible. The difference is quite large.
This will be O(millions * state_size) of flops per frame. A Kalman filter of the same state size will have the expense of a matrix invert, which will be O(state_size^3). So for a state size of, say, 12 floats, the Kalman will be about O(2000)-ish flops. A particle filter with "millions of points" modeling the same system will be O(state_size * millions * flops_per_state_update) which could be literally billions of flops, a six order of magnitude difference.
While there are absolutely applications where the particle filter is a more appropriate choice, it's just false to say that the performance difference is negligible. The difference is quite large.
You have an extra multiply there.
If you need, say, 50 ops per particle, and there's 1 million, and they're updated 10x per second, this is just 500 MFLOPS.
A typical recent-ish (not even latest-gen!) mobile GPU can handle something like 500 GFLOPS, more than 1000x the amount needed! https://news.ycombinator.com/item?id=16750535
You could even update the filter 1000x per second to track high-frequency motion and still only use 10% of the GPU power!
Obviously, some models need more ops per particle, more or less particles, or different update frequencies. However, consider that current-gen phones like the iPhone 13 are already at multiple TFLOPS, and this number will just keep going up over time.
There might be some really interesting algorithms unlocked once we're at the point where we can run particle filters "per pixel" on a video feed.
If you need, say, 50 ops per particle, and there's 1 million, and they're updated 10x per second, this is just 500 MFLOPS.
A typical recent-ish (not even latest-gen!) mobile GPU can handle something like 500 GFLOPS, more than 1000x the amount needed! https://news.ycombinator.com/item?id=16750535
You could even update the filter 1000x per second to track high-frequency motion and still only use 10% of the GPU power!
Obviously, some models need more ops per particle, more or less particles, or different update frequencies. However, consider that current-gen phones like the iPhone 13 are already at multiple TFLOPS, and this number will just keep going up over time.
There might be some really interesting algorithms unlocked once we're at the point where we can run particle filters "per pixel" on a video feed.
You're completely free to decide you're unbothered by it in your own particular application, but it would be unhelpfully misleading to other readers to say that a 10^6 performance difference is "negligible", or that they should expect the particle filter to give better results.
Particle filter is very cool, and it's great that someone mentioned it because it's quite useful in the right circumstances. But it is not a panacea (nor is the Kalman filter), and we don't need to misrepresent it in order to advocate for it in cases where it's applicable.
Particle filter is very cool, and it's great that someone mentioned it because it's quite useful in the right circumstances. But it is not a panacea (nor is the Kalman filter), and we don't need to misrepresent it in order to advocate for it in cases where it's applicable.
I didn't see you admit that a 6 order of magnitude difference isn't "negligible", as you originally claimed. Instead you're making the argument that we can throw hardware at the problem, which is fine, but a very different statement.
I expect people to disagree with me, but it's very hard to get past the condescending language in the article:
> Totally neat, crazy correlations, scary math, pretty pictures, shiny pictures
It's really hard to read past this. I've seen this tone occasionally from junior academic lectures who somehow think that talking to people like they are nervous children will help put them at ease. I don't think the author's doing this malociouly, but it comes across as "I'm so smart, but don't be afraid, I'm dumbing it down to a cutesy level you can understand"
Avoid writing like this if you can, it's clear from the comments the article is otherwise very good
> Totally neat, crazy correlations, scary math, pretty pictures, shiny pictures
It's really hard to read past this. I've seen this tone occasionally from junior academic lectures who somehow think that talking to people like they are nervous children will help put them at ease. I don't think the author's doing this malociouly, but it comes across as "I'm so smart, but don't be afraid, I'm dumbing it down to a cutesy level you can understand"
Avoid writing like this if you can, it's clear from the comments the article is otherwise very good
"Please don't pick the most provocative thing in an article and rush to the thread to complain about it. Find something interesting to comment about instead."
https://news.ycombinator.com/newsguidelines.html
https://news.ycombinator.com/newsguidelines.html
it's just the pop-sci writing style. You see this with lots of articles and content directed at a general audience - I think this author's just reused the same style to talk to a technical audience. It's not inherently condescending, it just comes across that way if you're writing for an audience of technical peers.
this kind of breathless style makes more sense when you don't expect the audience to be technically literate and the content is there to make them say "wow, I don't understand anything you're saying but there certainly are technical words in here!" - see, for instance, popular media around anything related to quantum mechanics.
this kind of breathless style makes more sense when you don't expect the audience to be technically literate and the content is there to make them say "wow, I don't understand anything you're saying but there certainly are technical words in here!" - see, for instance, popular media around anything related to quantum mechanics.
Of course I disagree. Your comment, which advises people not to write like the article, starts with phrase it's a waste of time to read. Then it misquotes the article—I was, naturally, expecting to see that quote in the article. It repeats a phrase, apparently for effect. "Malociouly"? You seem to see signs of humanity in the writer only as condescension and vanity. Your "Avoid writing like this" applies infinitely better to your own comment, I think.
You seem to assume all writing should be dry academic writing, without vivid language or friendliness to the reader.
You seem to assume all writing should be dry academic writing, without vivid language or friendliness to the reader.
I agree. From personal experience, this sort of phrasing comes during a temporary high that you get after mastering a topic. Conquering a piece of technical material elevates you, and in a sense you want to be condescending towards your ignorant past self.
It's bad taste.
It's bad taste.
rightbyte(4)
[1] https://cybernetist.com/2019/01/13/apollo-kalman-filter-and-...
[2] https://github.com/milosgajdos/go-estimate