Here is another way of using randomization:
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 signiﬁcantly 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.
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.