Title :
Fast perfect weighted resampling
Author_Institution :
Dept. of Comput. Sci., Portland State Univ., Portland, OR
fDate :
March 31 2008-April 4 2008
Abstract :
We describe an algorithm for perfect weighted-random resampling of a population with time complexity O(m + n) for resampling to inputs to produce n outputs. This algorithm is an incremental improvement over standard resampling algorithms. Our resampling algorithm is parallelizable, with linear speedup. Linear-time resampling yields notable performance improvements in our motivating example of sequential importance resampling for Bayesian particle filtering.
Keywords :
Bayes methods; computational complexity; importance sampling; particle filtering (numerical methods); signal sampling; Bayesian particle filtering; linear-time resampling; sequential importance resampling; time complexity; weighted-random resampling algorithm; Band pass filters; Bayesian methods; Computer science; Costs; Filtering; Particle tracking; Sampling methods; Sensor fusion; State estimation; State-space methods; Monte Carlo methods; filtering; state estimation; tracking filters;
Conference_Titel :
Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4244-1483-3
Electronic_ISBN :
1520-6149
DOI :
10.1109/ICASSP.2008.4518395
