Hacker News Reader

Comment by jongraehl | Hacker News Reader

I like particle filtering because it's easy to understand and implement - https://en.wikipedia.org/wiki/Monte_Carlo_localization - and it's correct even for non-gaussian uncertainty.

Is Kalman filtering computationally more efficient (obviously particle filtering is stochastic and so trades off accuracy for compute) or does it have some other advantage?

View on HN

Firstly, Kalman filtering is optimal, that is, it produces exactly the correct posterior distribution. As you mention, particle filters cannot achieve this.

It's a rough heuristic that to achieve a certain accuracy for a linear/Gaussian system with a particle filter, you need a number of particles exponential in the number of dimensions of the system. I feel like this could probably be stated more formally and shown, but I don't think I've seen anything in that vein. The Kalman filter, being simply matrix operations, should scale as the number of dimensions cubed.

So yes, Kalman filtering is computationally more efficient, and (obviously) more accurate.

I also wouldn't discount the fact that the Kalman filter is, in a sense, simpler than the particle filter for a linear/Gaussian system; you don't need to worry about resampling or setting a good number of particles, and you don't need to compute estimates of the mean/covariance statistics (which are sufficient since the posterior should be a Gaussian).

Under the same conditions of linearity and Gaussian noise you can get essentially optimal performance. Of course, why would you when the KF is so much more efficient.

This is true but the assumption of Gaussian noise carries with it the assumption that the model is correct.

Most models are not correct which is why particle filters perform much better than people expect.

Particle filters can be an option if the noise is not additive (e.g. scales with signal amplitude) and Gaussian.

Kalman Filters are super efficient to calculate - they're what kept the Apollo program on track (60s compute!). Another post gives the asymptotic complexity - but as a rule of thumb if you can do any practical computation at all you can run a Kalman Filter.

Basically they're both implementations of a recursive Bayesian filter, but the Kalman filter requires very strong assumptions about the distribution (all Gaussian) and the particle filter requires none.

The Kalman filter is optimal for the Gaussian case (and is very efficient to calculate), whilst the particle filter can use more accurate distributions but is far less efficient to calculate.

You kinda use them in different places - a Kalman filter is useless for pedestrian dead reckoning (step made + estimate of direction), whilst a particle filter would be similarly dumb on submarines.

True. Our robot uses a particle filter since we're mostly localization by odometry and lidar returns. But if we had an outdoors robot using GPS like the one in the article then our uncertainty would be a lot more Gaussian and I think we'd switch.

Also, for determining the position of your own robot the efficiency isn't a big deal. But if you're tracking a lot of objects in your environment then it becomes more important. And since you're looking at the objects and are tracking relative position the distribution is uni-modal too.

The KF is very efficient.

It's optimal for linear Gaussian systems and computation is polynomial in measurement dimensionality k and state dimensionality n:  

O(k^2.376 + n^2)

(Yes I had to look that up.)

Reply on news.ycombinator.com