5 ms·
Basis of the Kalman Filter [pdf]
- esafak 2y agoThey also had nice tutorials on particle filters. I can't find the one I wanted but these are close: https://cecas.clemson.edu/~ahoover/ece854/refs/Djuric-ParticleFilter.pdf https://cecas.clemson.edu/~ahoover/ece854/refs/Djuric-Partic... https://eprints.lancs.ac.uk/id/eprint/53537/1/Introduction_to_BPF_2013_IEEE_SPM.pdf https://eprints.lancs.ac.uk/id/eprint/53537/1/Introduction_t... https://ieeeoes.org/wp-content/uploads/2021/02/BPF_SPMag_07.pdf https://ieeeoes.org/wp-content/uploads/2021/02/BPF_SPMag_07....
- namibj 2y agoThanks, I'll see about Box-PF when trying to get IMU-filtered indoor-localization working (once I hopefully get that far with the UWB firmware [0]). Accounting for clock drift across the "satellites" is going to be "fun", but at least it's both useful in practice and of manageable complexity/scope. [0]: I'll happily talk about it at 39c3.
- jhoydich 2y agoPF is a great tool for UWB. Even without IMU data and instead adding uniform diffusion of the particles between updates tracking worked well in a 2D environment. It sounds like you're working on TDOA for UWB?
- brcmthrowaway 2y agoits a pity there are no good software packages for particle filters
- esafak 2y agoI haven't used them yet but I know of pyro, pfjax, and pymc: https://pyro.ai/examples/smcfilter.html https://pyro.ai/examples/smcfilter.html https://pfjax.readthedocs.io/ https://pfjax.readthedocs.io/ https://www.pymc.io/projects/examples/en/latest/samplers/SMC2_gaussians.html https://www.pymc.io/projects/examples/en/latest/samplers/SMC...
- jvanderbot 2y agoThe problem with this idea is that deriving all the propagation and measurement functions and associated jacobians is 99% of the problem. Once that's done you can implement literally any filter from them using Wikipedia.
- brcmthrowaway 2y agoParticle filters dont need jacobians?
- JohnKemeny 2y agoSee also Kalman Filter Explained Simply (2024, 89 comments) https://news.ycombinator.com/item?id=39343746 https://news.ycombinator.com/item?id=39343746 A non-mathematical introduction to Kalman filters for programmers (2023, 97 comments) https://news.ycombinator.com/item?id=36971975 https://news.ycombinator.com/item?id=36971975
- gradascent 2y agoI've found this "book" (series of jupyter notebooks) to be a fantastic course on the Kalman filter from basics to advanced topics. https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
- carabiner 2y agoKalman filter is the "learn python in 24 hours" for HN.
- zevv 2y agoAnd monads. But I've heard they're just like burritos, so how hard can it be.
- hansvm 2y agoThat probably depends on how much you overcook the burrito.
- rhet0rica 2y agoI love not knowing whether the "pdf" in the title (and URL) refers to a probability density function or the portable document format. ...The answer will surprise you!
- almostgotcaught 2y agoi don't know know why the hell people are so obsessed with it. like why aren't there recurring posts about how to solve a separable PDE or how to perform gram shmidt or whatever other ~junior math things.
- defrost 2y agoKalman filters are useful in data processing and interpretation, I used them heavily in continuous geophysical signal processing four decades past. My guess is that many computer data engineers encounter them and find their self taught grasp of linear algebra and undergraduate math challenged by the theory behind K-F's .. they seem to come across as a bit of a leg up over moving averages, Savitzky–Golay, FFT applications, etc. There are many more people dealing with implementing these things than have had formal undergraduate lectures on them. My gut feeling is that most are more likley to encounter K-F applications in drone control, dead reckoning positions when undergound or with flakey GPS, cleaning real world data, etc. than to find themselves having to solve PDE's .. I posit the existence of some form of pragmatic Maslow's Hierarchy of Applicable Math. I do agree though that HN has odd bursts of Kalman filter posts.
- adamnemecek 2y agoThe Kalman Filter is an instance of the Generalized Distributive Law https://en.wikipedia.org/wiki/Generalized_distributive_law https://en.wikipedia.org/wiki/Generalized_distributive_law So is the Fast Fourier transform, Viterbi algorithm, dynamic programming, message passing and a trillion other things.
- all2 2y agoCan you expand on how the Kalman Filter fits into this category?
- adamnemecek 2y agohttps://web.cs.ucla.edu/~yzsun/classes/2014Spring_CS7280/Papers/Probabilistic_Models/Constructing%20Free%20Energy%20Approximations%20and%20Generalized%20Belief%20Propagation%20Algorithms.pdf https://web.cs.ucla.edu/~yzsun/classes/2014Spring_CS7280/Pap...
- ckrapu 2y agoI've seen the Kalman filter presented from a few different angles and the one that made the most sense to me was the one from a Bayesian methods class that speaks only in terms of marginal and conditional Gaussian distributions and discards a long of the control theory terminology. This was one of the books we used: https://link.springer.com/chapter/10.1007/978-1-4757-9365-9_4 https://link.springer.com/chapter/10.1007/978-1-4757-9365-9_...
- jbullock35 2y agoI succeeded in understanding the Kalman filter only when I found a text that took a similar approach. It was this invaluable article, which presents the Kalman filter from a Bayesian perspective: Meinhold, Richard J., and Nozer D. Singpurwalla. 1983. "Understanding the Kalman Filter." American Statistician 37 (May): 123–27.
- chubs 2y agoAs a developer I always found these maths-first approaches to Kalman filters impenetrable (I guess that betrays my lack of knowledge, I dare cast no aspersions on the quality of these explanations!). However, if like me, it helps with the learning curve to implement it first, here's a 1-dimensional version simplified from my blog: function transpose(a) { return a } // 1x1 matrix eg a single value. function invert(a) { return 1/a } const qExternalNoiseVariance = 0.1 const rMeasurementNoiseVariance = 0.1 const fStateTransition = 1 let pStateError = 1 let xCurrentState = rawDataArray[0] for (const zMeasurement in rawDataArray) { const xPredicted = fStateTransition * xCurrentState const pPredicted = fStateTransition * pStateError * transpose(fStateTransition) + qExternalNoiseVariance const kKalmanGain = pPredicted * invert(pPredicted + rMeasurementNoiseVariance) pStateError = pPredicted - kKalmanGain * pPredicted xCurrentState = xPredicted + kKalmanGain * (zMeasurement - xPredicted) // Output! } https://www.splinter.com.au/2023/12/14/the-kalman-filter-for-programmers/ https://www.splinter.com.au/2023/12/14/the-kalman-filter-for...
- nextos 2y agoIt's not your fault, these can get messy very quickly. Infer.NET was started because Tom Minka and other Bayes experts were tired of writing message passing and variational inference by hand, which is both cumbersome and error prone on non-toy problems. It helps to take a more abstract view where you split the generative process and the inference algorithm. Some frameworks (Infer.NET, ForneyLab.jl) can generate an efficient inference algorithm from the generative model without any user input. See e.g. https://github.com/biaslab/ForneyLab.jl/blob/master/demo/kalman_smoother_2d.ipynb https://github.com/biaslab/ForneyLab.jl/blob/master/demo/kal...
- ngriffiths 2y agoThanks for sharing this - saving this paper too (from link in the github page): https://people.ee.ethz.ch/~loeliger/localpapers/FactorGraphsProcIEEE2007.pdf https://people.ee.ethz.ch/~loeliger/localpapers/FactorGraphs... I'm not familiar with these techniques at all but seems like they have a ton of useful applications.
- thundercarrot 2y agoIf Q and R are constant (as is usually the case), the gain quickly converges, such that the Kalman filter is just an exponential filter with a prediction step. For many people this is a lot easier to understand, and even matches how it is typically used, where Q and R are manually tuned until it “looks good” and never changed again. Moreover, there is just one gain to manually tune instead of multiple quantities Q and R.
- quietbritishjim 2y ago> If Q and R are constant (as is usually the case), the gain quickly converges, You also need for measurements to be equally spaced. Often they are – you might get an alternating pattern of measurement and observation – but often they're not, in which case the Kalman filter gives extra weight to new measurements coming in if it's been a while since it last had one (because that will have allowed the uncertainty to grow). The Kalman filter also allows you to take into account measurements that are more uncertain in one direction than another. Think of cameras with visual recognition, which tell you a precise angle but only a rough distance estimate. If you have a couple of those and suitable measurement error matrices then the Kalman filter will automatically do a sort of triangulation. Add a bonus, you can also use the covariance matrix of the target as information in its own right. But, as you say, often parameters are tuned for getting a good result rather than reality so the target uncertainty isn't always especially meaningful.
- pandemic_region 2y agoFor the lesser developer gods here, can someone give an example of a real life business case where (s)he has effectively used this? Explain like you're talking to a guy who has done CRUD most of his life.
- stormfather 2y agoSmoothing out messy data from an eye tracker into a smooth gaze path.
- kombine 2y agoI find this lecture series give a good introduction on Bayesian theory of filtering: https://www.youtube.com/watch?v=pVyltJnXlAI&list=PLTD_k0sZVYFqjFDkJV8GE2EwfxNK59fJY&index=12 https://www.youtube.com/watch?v=pVyltJnXlAI&list=PLTD_k0sZVY...
- aktenlage 2y agoIt took years after I learned the Kalman Filter as a student, until I actually intuitively understood the update of the covariances. Most learning sources (including the OP) just mechanically go through the computations of the a-posterior covariance, but don't bother with an intuition other than "this is the result of multiplying two gaussians", if anything at all. I wrote down a note for myself where I work this out, if anyone is interested: https://postbits.de/kalman-measurement-update.html https://postbits.de/kalman-measurement-update.html
- aktenlage 2y agoFigured I can save you a click and put the main point here, as few people will be interested in the rest: The Kalman filter is adding the precision (inverse of covariance) of the measurement and the precision of the predicted state, to obtain the precision of the corrected state. To do so, the respective covariance matrices are first inverted, to obtain precision matrices. To have both in the same space, the measurement precision matrix is projected to the state space using matrix H. The resulting sum is converted back to a covariance matrix, by inverting it.
- lawrenceyan 2y agoIn the realm of autonomous vehicles, early sensor fusion systems relied heavily on the usage of Kalman Filters for perception. The state of the art has now been supplanted by large deep learning models in the present day, primarily relying on end-to-end trained Transformer networks. This may be familiar to you in the context of LLMs which have recently become popular, but they were actually first successfully utilized in autonomous vehicles (invented by researchers at Google and implemented in production at Waymo almost immediately).