Kalman Filter Explained Simply
thekalmanfilter.com
thekalmanfilter.com
https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
That book mentions alpha-beta filters as sort of a younger sibling to full-blown Kalman filters. I recently had need of something like this at work, and started doing a bunch of reading. Eventually I realized that alpha-beta filters (and the whole Kalman family) is very focused on predicting the near future, whereas what I really needed was just a way to smooth historical data.
So I started reading in that direction, came across "double exponential smoothing" which seemed perfect for my use-case, and as I went into it I realized... it's just the alpha-beta filter again, but now with different names for all the variables :(
I can't help feeling like this entire neighborhood of math rests on a few common fundamental theories, but because different disciplines arrived at the same systems via different approaches, they end up sounding a little different and the commonality is obscured. Something about power series, Euler's number, gradient descent, filters, feedback systems, general system theory... it feels to me like there's a relatively small kernel of intuitive understanding at the heart of all that stuff, which could end up making glorious sense of a lot of mathematics if I could only grasp it.
Somebody help me out, here!
I read Feedback Control for Computer Systems not too long ago, which felt like yet another restatement of the same ideas; I guess that counts as "classic control theory".
Here is a broad survey: https://people.bordeaux.inria.fr/pierre.delmoral/chen_bayesi...
I do feel like the core of it is essentially exponential/logarithmic growth/decay, with the option to layer multiple higher-order growth/decay series on top of one another. Maybe that's the gist...
While it uses letters so it looks vaguely like writing, math notation is very pictorial in nature. Long words would obscure the pictures.
- Using long descriptive variable names would give them meaning, and make the particular equation/expression easier to understand or apply.
- Using short single-letter variable names allows you to forget the meaning of the variables and see the underlying structure, thus making the expression easier to connect to other situations (with completely unrelated meanings) that happen to have the same underlying structure. (The letters being meaningless, or at least not carrying their meaning so strongly, is a feature, not a bug.)
(See the highest-voted answer to https://math.stackexchange.com/questions/24241/why-do-mathem... for example.)
(Another way of seeing the distinction is whether you consider the equation to be the final result, to be used and applied, or as a starting point, to be manipulated further.)
Edit: I realise, like someone mentioned in another comment, that sometimes you also want to make the pattern visible to readers.
The thing about math is you need to be comfortable viewing the same concept through a bunch of different lenses, and various notations are meant to help you do that by emphasizing different aspects of "the picture" you're looking at.
It's like either they're not clear who their audience is or they're afraid to get off the beaten path. If they're explaining a classic algorithm, they use the common, single-letter variables instead of replacing them with meaningful names.
The real intuition is "everything is a filter." Everything else is about analysis and synthesis of that idea.
The thing about Kalman filter is that its a pretty well known and exists in many software packages (just like PID) so its fairly easy to implement. But because noise is often not gaussian, and systems are often not linear, its more of a "works well enough" for most applications.
https://www.splinter.com.au/2023/12/14/the-kalman-filter-for...
https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit...
As a developer I found the maths made sense only after implementing it, ironically. I guess we learn by building on top of what we already know? Is there a term for that?
Also when this person says the subscript "denotes the order of the measurement" I'm trying to figure out what kind of order he's talking about. I guess that's the index? It's been a while since I did kalman filters:-p
Same when something is named descriptively: shield volcano, star dunes, vs. some person’s name like Rayleigh scattering.
It’s just an extra layer to memorize and parse.
In math/physics/engineering the terminology is unfamiliar at first but very precise and hence learnable. The vast majority of STEM textbooks (at least from good US university publishers) make their best effort in presenting the material understandably without any intentional obscurantism or additional fanciness. Academic joirnal/conference papers do sometimes intentionally confuse to game the publication metrics but intro materials are an earnest effort at educating. The subject matter has some inherent complexity, there's no need to prop it up artificially for prestige (that happens more in other fields that are insecure about their level of inherent complexity).
The more pure the mathematics the shorter the scope of most variables. Typically a variable is defined just before it's used, with a scope no longer than the proof or derivation it's in.
Also some of the choices in this article are just plain silly. Such as using P as both variable and index, and then use it for the covariance matrix when the precision matrix is the exact inverse.
Usually the stuff I'm implementing is complicated enough that reading the code without reading the paper won't have much meaning. And if you're reading the paper, it's good to have as close to a 1-1 representation to help give confidence that I implemented it right.
I've had non-zero times where I took his pseudocode, pasted it into my IDE and did a search and replace of begin/end to braces and "<-" to "=" and it "just worked" on the first try. I always found that amazing that he could write this stuff without ever trying it (outside of his head).
* r,g,b,a
* h,s,l
* x,y,z
If you want people to understand, you skip the mathematical notation and use pseudocode, or at least you start with an explaination and once people know what they are looking at you go into the math notation.
I understand that mathematical notation can be very practical for describing a certain class of problems concisely, but especially if you teach or explain things, consider that being concise is meaningless if people don't understand what you describe.
Sometimes my feeling is that this is on purpose. People not understanding what you are doing (but you come across soo smart), is a feature to many. Even better: The layperson cannot tell whether you are talking utter gibberish or using the most precise language on earth.
I, however, think you can recognize real smart people by the phenomenon that every room they are in seems to become smarter in total, because they lift people up in their wake of understanding things so deeply, they can just break them down into their very simple, managable parts and translate obscure domain-specific languages into something people can grasp.
I too can go into deep domain specific lanuages, be it in philosophy, electrical regulation, film theory, programming lingo, music theory, control theory etc. But what is the point of doing that without making the person opposite understand what you're waffling on about? Because either you will seem like a knowledgeable person that has a total lack of self-perception or like a brick that doesn't care what message reaches the person opposite as long as rhey can hear themselves talk.
That being said: Domain-specific language can be okay if it is used between people within that domain. But I have met many physicists or mathematicians who also think math notation sucks, so maybe there could be something better.
I still haven't quite forgiven the writers of UMAP for writing a theorem that uses pi^n/2 / Gamma(n/2+1) instead of the more reasonable "volume of the unit sphere". It makes it so confusing that they fail to spot the theorem doesn't work for low dimensional objects embedded in high dimensional spaces, which is their exact use-case. Luckily their informal conclusion does work, mostly.
The order referred to is the index-in-time that a value correspond to. Eg, x_3 would be the state at the third time step. I think their subscript “p” stands for prediction. x_p at time 3 is the state we expect at time 4. But then when time 4 comes around, we incorporate new measurements and calculate x_4 including that new information. Just to be explicit, this x_4 will be different from the x_p we calculated at time 3, as our prediction is always a bit incorrect
I hate that the most when reading papers. Authors trying to sound abstract and academic, but only accomplishing being frustratingly vague. AUTHORS YOU STILL HAVE TO INSERT THE SUBJECT INTO YOUR SENTENCES FOR THEM TO MAKE SENSE.
I'm so frustrated at this aspect in research papers more than anything else. You must disambiguate. Use absolute descriptors and do not use relative descriptors. Don't tell me to look right, because I'll look left. Use absolute descriptors! "then after spinning the prism the light cone blah blah blah" SPIN!? SPIN IN WHAT DIRECTION????? LEFT?RIGHT?! LATERAL? UP? DOWN???? How fast? How slow? You imagine all of these CRITICAL ASPECTS in your head when writing such ambiguous sentences, but the reader cannot read your mind.
I think the variable names are already picked to be descriptive. No one is picking them to be more obscure or harder to track. The problem is that those who are starting out still haven't picked up concepts or learned the standard notations for each problem domain, thus we are left with the pain of ramping up on a topic.
I was for example reading a cryptography book and it has symbols like a hamadad product.
https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d2...
Here's a formula for calculating the downstream Mach number in a certain kind of supersonic flow. I cannot imagine any way to write this in "descriptive variables" which makes the formula understandable at all, you just could not see the structure. (from https://en.wikipedia.org/wiki/Oblique_shock )
For reference, the Wikipedia page "Order (mathematics)" is a disambiguation page almost as long as the top-level disambiguation page "Order".
https://en.wikipedia.org/wiki/Order_(mathematics)
I generally don't have a problem with variable names, but creating syntax and terminology that conflicts with other mathematical use is a real problem.
I mean what you're really doing is take a measurement then simulate the possible future states and combine this information with the next measurement and repeat.
You can imagine e.g. taking multiple pictures of a tennis-ball, estimate its position and speed from the first picture, simulate where it's going to end up, and compare this with the next picture to see which estimate is closer to the truth. Or more old school, measure the inclination of the sun and compare the resulting line of possible locations on a map to the spot you thought you were.
Of course the exact calculations are beyond impractical. So you use sampling to simplify. However that still makes it difficult so you assume the distribution is somewhat close to a Gaussian distribution. And then you simplify even more by assuming the evolution of the system is just a linear transformation. And that's how you end up with the Kalman filter discussed here.
I'd be amazed if anyone could really understand what's going on just based on the linear algebra.
The kalman filter tries to guess the hidden input that produced the measurements. It does so forming the minimization problem:
'minimize over x, the function [ actual_measurement - expected_measurement(x) ]^2/s^2', here 's' is sigma of noise.
This follows from the state estimation problem:
'maximize over x, the likelihood of seeing the actual_measurement', because the only term that matters in the likelihood function is -([x-expected(x)]/s )^2. (look at the exponent in the Normal distribution, or any exponential distribution really).
'actual_measurement' is a constant, so if it happens that the function 'expected_measurement' is linear, this is trivially solved directly as a convex optimization, and if you take derivative, equate to zero, and solve, you'll get the kalman filter update step.
If it so happens that the function is non-linear, well we just make a single netwton-rhapson step by linearizing the equation, minimizing, and returning the solution to the "pretend linearization".
This is basic calc + linear algebra at an undergrad level, but nobody bothered to tell you that.
---
It's also completely wrong. It's a hack from the 60s to maximize the likelihood function using a recursive, single-step linearization like this. A misreading of the Cramer Rao Lower Bound has "proven" to generations of engineers that this is optimal. It's not, not really.[^1]
Nowadays we have 10,000x more compute, and any one of the following _will_ produce better performance:
* Forming and solving the non-linear equation using many newton-rhapson steps
* Keeping a long history of measurements, and solving using many newton-rhapson steps over this batch
* Using sum-of-guassian representation to accomodate multi-modal measurement functions, esp when including the prior bullets
All of these were well covered by state estimation research from 80s to now, but again, the textbooks seem to be written in stone in 1972.
[^1]: (the cramer rao lower bound is only defined when all measurement likelihood functions are linearized at the true state - which is only possible asymptotically in a batch which preserves all the measurements - and not possible before time infinity and not possible with recursive filter)
Do you have any good resources (online or textbook) you could recommend, as an introduction to these concepts, that is more modern / up-to-date?
You could do fine by reading some old books by Bar-Shalom. Any practical textbook like his would include all the "other stuff" about the EKF that helps you understand how nonperforming it often is.
But the actual derivation of the EKF is probably only one or two pages in such a textbook, which is a damn shame nobody includes it.
The background required is simply:
* Know the form of exponential family of PDFs (like Normal Gaussian)
* Bayes rule
* Recognize that to maximize f~= exp(-a), you have to minimize 'a'
* Know how to take derivative of matrix equation ('a', above)
* Solve it
* Use 'matrix inversion lemma' to transform solution to what KF/EKF provides.
Ah hell, I'll just write it up.
The problems of the filter are present in both.
[1] That is, it is generally easier to approximate a distribution than a non linear function.
Your comment is the first I've seen actually providing intuition about what is happening. It doesn't help perhaps that the name itself is misleading as heck to computer people like me: it's not a filter as in stream processing or SQL.
- simple to predict / understand what it would do: Easily explained with pictures and hardly no math
- simple to understand at a higher level / see why it works: Not easily explained without math and fraught with bayesian vs optimization vs EE-type approaches
- simple to understand well enough to use: Not easily done without other relevant math that is not covered in KF explanation, e.g., controls, matrix analysis, Jacobians, etc
- simple to understand why the equations are named what they are, and why they work: Not easily explained without math and historical context that takes a page or so to explain.
> it's not a filter as in stream processing
As you say "filter" means 'remove noise', but it also means 'process in order of arrival', so it's similar to your def of filter.
So, we really need 4 guides.
filter: use measurements up to time t to estimate the state at time t
smooth: use past and future measurements to estimate the state at time t
predict: use measurements up to time t to estimate the state at time t+n
https://praveshkoirala.com/2023/06/13/a-non-mathematical-int...
But IME everyone in the entire world is a "visual learner" who learns best by examples. So I'm surprised that the tutorial midway through the page doesn't put any example numbers into the formulas (maybe I glanced over it?) and the pictures only start after a page of "what is a Kalman filter" text, and the pictures are just of more formulas.
That last bit, using an observation to update a belief on a state variable, that's what the Kalman filter does.
In a way it is like a primitive RNN, it has internal state, inputs and outputs.
Also common in robotics applications is the Particle Filter, which uses a Monte Carlo approximation of the uncertainty in the state, rather than enforcing a (Gaussian) distribution, as in the traditional Kalman filter. This can be useful when the mechanics are highly nonlinear and/or your measurement uncertainties are, well, very non-Gaussian. Sebastian Thrun (a CMU robotics professor in the DARPA "Grand Challenge" days of self-driving cars) made an early Udacity course on Particle Filters.
A similar thing happens that had the word quantic or relativistic. I'm a physicist and we hardly talk about it, but here in HN we find people bringing in up every other day
Some theories even suggest that Kalman filtering (or a similar algorithm) provides a basis for neurobiological learning. See predictive coding (e.g. https://arxiv.org/pdf/2102.10021.pdf)
(Why I'm interested in it, at least.)