How a Kalman filter works, in pictures
bzarg.com
bzarg.com
[1] https://cybernetist.com/2019/01/13/apollo-kalman-filter-and-...
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.
That seems... excessive.
Someone once joked that all of sensing and estimation (and path planning and optimal control) is just applied convex minimization.
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...
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 is also the only technical book I have read that aptly quotes Shakespeare: "Age cannot whither her, nor custom stale her infinite variety."
For some reason I rarely see it being described as such.
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.
Here, we’re iteratively incorporating measurements along the trajectory, finally arriving at basically a least squares fit result, after a backward smoothing pass.
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?
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.
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?
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'.
[1] https://crates.io/crates/adskalman [2] https://github.com/strawlab/adskalman-rs/blob/main/examples/...
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.
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.
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.
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.
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.
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.
> 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
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.
You seem to assume all writing should be dry academic writing, without vivid language or friendliness to the reader.
It's bad taste.