3 ms·

Kalman filters might be one of those weird cases in mathematics where the 'simple' version is simplified beyond all recognition. I mean what you're really doin

Kalman filters might be one of those weird cases in mathematics where the 'simple' version is simplified beyond all recognition. 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.

jvanderbot 3y ago
It's simpler than that. The linear algebra is actually easier. 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)
- palebluedot 3y ago
  > 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. 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?
  - jvanderbot 3y ago
    I don't, sadly. The only coverage of this that was first-principles accessible was the course taught by Prof Stergios Romelioutis where I went to grad school. 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.
  - markisus 3y ago
    Probabilistic Robotics covers Kalman Filter from a first principles probabilistic viewpoint, and its extension the EKF. It's quite readable for someone with basic understanding of linear algebra, probability, and calculus. I believe it also has a refresher on these basics in the introduction. http://www.probabilistic-robotics.org/ http://www.probabilistic-robotics.org/
- eutectic 3y ago
  Both the Bayesian perspective and the optimization perspectice are legitimate ways of understanding the Kalman filter. I like the Bayesian perspective better.
  - jvanderbot 3y ago
    Forgive me, I'm thoroughly confused by that dichotomy. How are they different? Approaching from bayes rule or a "maximum likelihood" approach produces the same results. The problems of the filter are present in both.
foobarian 3y ago
I don't know what it is about the Kalman filter but so many explanations including the OP have this format: "It's very simple! <complicated obtuse explanation listing the computation steps>" 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.
- shiandow 3y ago
  I recall reading a very intuitive explanation including animations of a point cloud to show how it works. I've had no luck finding the article again though.
- jvanderbot 3y ago
  The problem is 'simple' can mean a few things: - 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.
- dwrtz 3y ago
  yeah the "filter" term means something different in the KF context and is confusing 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

jvanderbot 3y ago

It's simpler than that. The linear algebra is actually easier. 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)

palebluedot 3y ago
> 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. 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?
- jvanderbot 3y ago
  I don't, sadly. The only coverage of this that was first-principles accessible was the course taught by Prof Stergios Romelioutis where I went to grad school. 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.
- markisus 3y ago
  Probabilistic Robotics covers Kalman Filter from a first principles probabilistic viewpoint, and its extension the EKF. It's quite readable for someone with basic understanding of linear algebra, probability, and calculus. I believe it also has a refresher on these basics in the introduction. http://www.probabilistic-robotics.org/ http://www.probabilistic-robotics.org/
eutectic 3y ago
Both the Bayesian perspective and the optimization perspectice are legitimate ways of understanding the Kalman filter. I like the Bayesian perspective better.
- jvanderbot 3y ago
  Forgive me, I'm thoroughly confused by that dichotomy. How are they different? Approaching from bayes rule or a "maximum likelihood" approach produces the same results. The problems of the filter are present in both.

foobarian 3y ago

I don't know what it is about the Kalman filter but so many explanations including the OP have this format: "It's very simple! <complicated obtuse explanation listing the computation steps>" 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.

shiandow 3y ago
I recall reading a very intuitive explanation including animations of a point cloud to show how it works. I've had no luck finding the article again though.
jvanderbot 3y ago
The problem is 'simple' can mean a few things: - 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.
dwrtz 3y ago
yeah the "filter" term means something different in the KF context and is confusing 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