DocumentCode
3419395
Title
Fast perfect weighted resampling
Author
Massey, Bart
Author_Institution
Dept. of Comput. Sci., Portland State Univ., Portland, OR
fYear
2008
fDate
March 31 2008-April 4 2008
Firstpage
3457
Lastpage
3460
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on
Conference_Location
Las Vegas, NV
ISSN
1520-6149
Print_ISBN
978-1-4244-1483-3
Electronic_ISBN
1520-6149
Type
conf
DOI
10.1109/ICASSP.2008.4518395
Filename
4518395
Link To Document