BMPF: Bayesian Mega-Particle Filtering

I've developed an algorithm, new to the best of my knowledge, for perfect linear-time weighted resampling of a distribution. This enables fast Bayesian Particle Filtering with extremely high particle densities, without concern for correct resampling. The algorithm is not a big advance on the state of the art, but it seems like a nice piece of work.

Right now, I can run BPF on a toy problem in 0.1 sec steps at about 140,000 particles in "real time", on my fast Core II Duo box. I call the code "Mega-Particle" because I am already achieving about 1.4M particle updates per second on a fast machine—resampling at each update. However, resampling is not the bottleneck step now, making this number somewhat arbitrary from the point of view of this research.

I've written a large draft paper on my work so far, as well as a much shorter paper submitted to ICASSP 2008. I also have made the source code of my GPL-licensed sample implementation of BMPF available: you can clone the GIT repository at git:// to get the complete revision history.

To build my BMPF code you'll currently also need my Ziggurat code—switching to it removed the first constant-factor bottleneck in my BMPF implementation, approximately doubling the speed. You may also find it useful in general. You might also want to take a look at the fast approximate exp() I found and re-implemented, which removed another bottleneck. I've also done work on table-driven sin() and cos() that attacks that performance bottleneck, and cleaned up and optimized the C code.