Accelerating Particle Filter using Randomized Multiscale and Fast Multipole Type Methods

Here is another way of using randomization:

Accelerating Particle Filter using Randomized Multiscale and Fast Multipole Type Methods by Gil Shabat, Yaniv Shmueli, Amit Bermanis and Amir Averbuch. The abstract reads:

We present a multiscale based method that accelerates the Particle Filter computation. Particle Filter is a powerful method that tracks the state of a target based on non-linear observations. Unlike the conventional way that calculates weights over all particles in each cycle of the algorithm, we sample a small subset from the source particles using matrix decomposition methods. Then, we apply a function extension algorithm that uses the particle subset to recover the density function for all the rest of the particles. As often happens, the computational effort is substantial especially when tracking multiple objects takes place. The proposed algorithm reduces significantly the computational load. By using the Fast Gaussian Transform, the particle selection step changes from O(k2n log n) operations to O(n + k log n) operations where n is the number of particles and k the selected subset size. We demonstrate our method on both simulated and on real data such as tracking in videos sequences.

Join our Reddit Experiment, Join the CompressiveSensing subreddit and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.