9 ms·
How a Kalman filter works, in pictures
- mgaunard 5y agoThe 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.
- nextaccountic 5y agoWhat's the "recursive" part? It's like the difference between IIR and FIR?
- gugagore 5y agoThat 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 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.
- ephimetheus 5y agoWe 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.
- chmaynard 5y ago(2015) https://news.ycombinator.com/from?site=bzarg.com https://news.ycombinator.com/from?site=bzarg.com
- chillingeffect 5y agodown atm. https://archive.md/cLjvZ https://archive.md/cLjvZ
- rightbyte 5y ago"I have to tell you about the Kalman filter, because what it does is pretty damn amazing." Not really, no. Kalman filters are the optimal way of removing white noise from simulations you yourself are adding. Good luck getting the covariance matrix right in practice. Usually it is diagonal and essentially a simple low pass filter with a fancy name.
- minihat 5y agoDear HN: Please don't let this comment discourage you from reading the article. Kalman filters are super useful tools across many domains. They are a primary instrument in weather forecasting, robotics, finance, and more. Data you see every day have been touched by this technology.
- ianai 5y agoThanks for your contextualization. The above comment really did hurt my desire to learn more about Kalman filters. I know just being negative or contrary to a thing has an unreasonably high return on investment in making a commenter look smart or authoritative, but it sure does harm.
- vlovich123 5y agoTo add onto this, it’s used in multiple places in GPS and other positioning problems (as in I was on the CoreLocation team at Apple years ago and Kalman filters were common). I’m not really sure where the commenter is sourcing their claim but my experience directly contradicts it.
- rightbyte 5y agoThe article is very good and pedagogical. My take on Kalman filter is that they are, with a diagonal regression matrix and precomputed parameters, just a convoluted notation for guesswork. It is abit like drawing Nyquist diagrams for system stability analysis - mostly an academic excercise. And stuff like that plagues control theory. I would rather that students learned to keep it simple.
- 5y ago
- michelpp 5y agoMichel van Biezen has an excellent video series on Kalman filters: https://www.youtube.com/watch?v=CaCcOwJPytQ 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.
- moffkalast 5y ago> The Kalman Filter (video 1 of 55) That seems... excessive.
- persedes 5y agoit'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.
- sp332 5y agoHe got to 42 https://m.youtube.com/playlist?list=PLX2gX-ftPVXU3oUFNATxGXY90AULiqnWT https://m.youtube.com/playlist?list=PLX2gX-ftPVXU3oUFNATxGXY...
- iamcreasy 5y agoAverage length of these videos are 5 minutes.
- jvanderbot 5y agoThe 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.
- NougatRillettes 5y agoNice. I wrote up another possible derivation here https://ngr.yt/blog/kalman/ https://ngr.yt/blog/kalman/ in case anyone is interested.
- xaedes 5y agoWelford'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.
- east2west 5y agoThe 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."
- InnerGargoyle 5y agothx for the suggestion.
- 6gvONxR4sf7o 5y agoWhere 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.
- artemisyna 5y agoI 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.
- sydthrowaway 5y agoWhere do you use it?
- quda 5y agoThe article starts nicely but soon ends up in the mud of math mysticism: K′=PkHTk(HkPkHTk+Rk)−1.... Useless.
- gyre007 5y agoCouple of years ago I blogged about how it was developed for the Apollo program [1] and then I wrote an implementation of different variations of it in Go [2]. [1] https://cybernetist.com/2019/01/13/apollo-kalman-filter-and-go/ https://cybernetist.com/2019/01/13/apollo-kalman-filter-and-... [2] https://github.com/milosgajdos/go-estimate https://github.com/milosgajdos/go-estimate
- rland 5y agoThis 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-Python/ https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
- stavros 5y agoExcellent, 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.
- CornCobs 5y agoSeconded! 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.
- mrguyorama 5y agoUnfortunately 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?
- jacksonkmarley 5y ago> 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'.
- east2west 5y agoI 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.
- jacksonkmarley 5y agoThanks for the suggestion!
- dbcurtis 5y agoTotally 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).
- east2west 5y agoI 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.
- albinofrenchy 5y agoI'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.
- leeoniya 5y agosomewhat related fft/data smoothing: https://dawn.cs.stanford.edu/2017/08/07/asap/ 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 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?
- version_five 5y agoI 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
- beaconstudios 5y agoit'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.
- yesenadam 5y agoOf 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.
- bigdict 5y agoI 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.
- maCDzP 5y agoI think of it as an algorithm for Bayes theorem - is that right?
- iamcreasy 5y agoBayes filter - yes.
- jiggawatts 5y agoA 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…
- tbabb 5y agoAuthor 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.
- jiggawatts 5y ago> 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.
- tbabb 5y ago> 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.
- sklargh 5y agoWhen 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.
- macrolocal 5y agoAs a matter of principle, I feel like this excellent article should contain contain the term "Bayesian update."
- bGl2YW5j 5y agoAwesome 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.
- ggm 5y agoAlthough 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.
- Rainymood 5y agoI 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!