Hacker News Reader

Comment by tbabb | Hacker News Reader

> but in practice the difference is negligible [...] A particle filter with a million points is trivial

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.

View on HN

You have an extra multiply there.

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.

You're completely free to decide you're unbothered by it in your own particular application, but it would be unhelpfully misleading to other readers to say that a 10^6 performance difference is "negligible", or that they should expect the particle filter to give better results.

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.

I didn't see you admit that a 6 order of magnitude difference isn't "negligible", as you originally claimed. Instead you're making the argument that we can throw hardware at the problem, which is fine, but a very different statement.

Reply on news.ycombinator.com