2013

Parallel resampling in the particle filter

Murray, Lawrence M., Lee, Anthony, Jacob, Pierre E.

Understand

Modern parallel computing devices, such as the graphics processing unit (GPU), have gained significant traction in scientific and statistical computing.

They are particularly well-suited to data-parallel algorithms such as the particle filter, or more generally Sequential Monte Carlo (SMC), which are increasingly used in statistical inference.
SMC methods carry a set of weighted particles through repeated propagation, weighting and resampling steps.
The propagation and weighting steps are straightforward to parallelise, as they require only independent operations on each particle.

Built on

Equation of state calculations by fast computing machines
Metropolis, N., A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller (1953) · 1953
Earlier work this paper cites.
A new approach to linear filtering and prediction problems
Kalman, R. (1960) · 1960
Earlier work this paper cites.
Generating sorted lists of random numbers
Bentley, J. L. and J. B. Saxe (1979) · 1979
Earlier work this paper cites.
Novel approach to nonlinear/non-Gaussian Bayesian state estimation
Gordon, N., D. Salmond, and A. Smith (1993) · 1993
Earlier work this paper cites.
Blind deconvolution via sequential imputations
Liu, J. S. and R. Chen (1995) · 1995
Earlier work this paper cites.
Monte Carlo filter and smoother for non-Gaussian nonlinear state space models
Kitagawa, G. (1996) · 1996
Earlier work this paper cites.
Metropolized independent sampling with comparisons to rejection sampling and importance sampling
Liu, J. S. (1996) · 1996
Earlier work this paper cites.
DIEHARD: a battery of tests of randomness
Marsaglia, G. (1996) · 1996
Earlier work this paper cites.
Rates of convergence of the Hastings and Metropolis algorithms
Mengersen, K. L. and R. L. Tweedie (1996) · 1996
Earlier work this paper cites.
Sequential Monte-Carlo methods for dynamic systems
Liu, J. S. and R. Chen (1998) · 1998
Earlier work this paper cites.
Rejection control and sequential importance sampling
Liu, J. S., R. Chen, and W. H. Wong (1998) · 1998
Earlier work this paper cites.
Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator
Matsumoto, M. and T. Nishimura (1998) · 1998
Earlier work this paper cites.
Sequential Monte Carlo Methods in Practice
Doucet, A., N. de Freitas, and N. Gordon (Eds.) (2001) · 2001
Earlier work this paper cites.
Parallel particle filtering
Brun, O., V. Teuliere, and J.-M. Garcia (2002) · 2002
Earlier work this paper cites.
A sequential particle filter method for static models
Chopin, N. (2002) · 2002
Earlier work this paper cites.
Xorshift RNGs
Marsaglia, G. (2003) · 2003
Earlier work this paper cites.
Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications
Del Moral, P. (2004) · 2004
Earlier work this paper cites.

Similar

Resampling algorithms and architectures for distributed particle filters
Bolić, M., P. M. Djurić, and S. Hong (2005) · 2005
Cited alongside, same era.
Comparison of resampling schemes for particle filtering
Douc, R. and O. Cappé (2005, 15-17) · 2005
Cited alongside, same era.
Sequential Monte Carlo samplers
Del Moral, P., A. Doucet, and A. Jasra (2006) · 2006
Cited alongside, same era.
Fast particle smoothing: If I had a million particles
Klaas, M., M. Briers, N. de Freitas, A. Doucet, S. Maskell, and D. Lung (2006) · 2006
Cited alongside, same era.
A single instruction multiple data particle filter
Maskell, S., B. Alun-Jones, and M. Macleod (2006, Sept) · 2006
Cited alongside, same era.
GPU Gems 3
Harris, M., S. Sengupta, and J. D. Owens (2007) · 2007
Cited alongside, same era.
TestU01: A C library for empirical testing of random number generators
L’Ecuyer, P. and R. Simard (2007) · 2007
Cited alongside, same era.
On the expectation of the maximum of IID geometric random variables
Eisenberg, B. (2008) · 2008
Cited alongside, same era.
Understanding the efficiency of ray traversal on GPUs
Aila, T. and S. Laine (2009) · 2009
Cited alongside, same era.
Designing efficient sorting algorithms for manycore GPUs
Satish, N., M. Harris, and M. Garland (2009, May) · 2009
Cited alongside, same era.
Particle Markov chain Monte Carlo methods
Andrieu, C., A. Doucet, and R. Holenstein (2010) · 2010
Cited alongside, same era.
Efficient parallelized particle filter design on CUDA
Chao, M.-A., C.-Y. Chu, C.-H. Chao, and A.-Y. Wu (2010, Oct) · 2010
Cited alongside, same era.

Then

GPU acceleration of the particle filter: The Metropolis resampler
Murray, L. M. (2011) · 2011
Later among the works it cites.
Chapter 26 - Thrust: A productivity-oriented library for CUDA
Bell, N. and J. Hoberock (2012) · 2012
Later among the works it cites.
Phylogenetic inference via sequential Monte Carlo
Bouchard-Côté, A., S. Sankararaman, and M. I. Jordan (2012) · 2012
Later among the works it cites.
Sequential monte carlo for rare event estimation
Cérou, F., P. Del Moral, T. Furon, and A. Guyader (2012) · 2012
Later among the works it cites.
A parallel resampling algorithm for particle filtering on shared-memory architectures
Gong, P., Y. Basciftci, and F. Ozguner (2012, May) · 2012
Later among the works it cites.
A custom precision based architecture for accelerating parallel tempering MCMC on FPGAs without introducing sampling error
Mingas, G. and C.-S. Bouganis (2012) · 2012
Later among the works it cites.
GPU acceleration of Runge–Kutta integrators
Murray, L. M. (2012) · 2012
Later among the works it cites.
High-performance pseudo-random number generation on graphics processing units
Nandapalan, N., R. P. Brent, L. M. Murray, and A. P. Rendell (2012) · 2012
Later among the works it cites.
CUDA Toolkit 5.0 CURAND Library
NVIDIA Corporation (2012, July) · 2012
Later among the works it cites.
Non-asymptotic error bounds for sequential mcmc methods in multimodal settings
Original
Schweizer, N. (2012) · 2012
Later among the works it cites.
Bayesian state-space modelling on high-performance hardware using LibBi
Murray, L. M. (2013) · 2013
Closest in time.
Sequential monte carlo on large binary sampling spaces
Schäfer, C. and N. Chopin (2013) · 2013
Closest in time.
On the role of interaction in sequential Monte Carlo algorithms
Whiteley, N., A. Lee, and K. Heine (2013) · 2013
Closest in time.
Towards automatic model comparison: an adaptive sequential monte carlo approach
Original
Zhou, Y., A. M. Johansen, and J. A. Aston (2013) · 2013
Closest in time.
Computational aspects of sequential Monte Carlo filter and smoother
Kitagawa, G. (2014) · 2014
Closest in time.
Sequential Monte Carlo for graphical models
Naesseth, C. A., F. Lindsten, and T. B. Schön (2014) · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…