IRUS Total

The chopthin algorithm for resampling

File Description SizeFormat 
chopthin.pdfAccepted version739.97 kBUnknownView/Open
Title: The chopthin algorithm for resampling
Authors: Gandy, A
Lau, F
Item Type: Journal Article
Abstract: Resampling is a standard step in particle filters and more generally sequential Monte Carlo methods. We present an algorithm, called chopthin, for resampling weighted particles. In contrast to standard resampling methods the algorithm does not produce a set of equally weighted particles; instead it merely enforces an upper bound on the ratio between the weights. Simulation studies show that the chopthin algorithm consistently outperforms standard resampling methods. The algorithms chops up particles with large weight and thins out particles with low weight, hence its name. It implicitly guarantees a lower bound on the effective sample size. The algorithm can be implemented efficiently, making it practically useful. We show that the expected computational effort is linear in the number of particles. Implementations for C++, R (on CRAN), Python and Matlab are available.
Issue Date: 6-Jul-2016
Date of Acceptance: 6-Apr-2016
URI: http://hdl.handle.net/10044/1/30887
ISSN: 1941-0476
Publisher: IEEE
Journal / Book Title: IEEE Transactions on Signal Processing
Volume: 64
Issue: 16
Copyright Statement: © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Keywords: MD Multidisciplinary
Publication Status: Published
Appears in Collections:Statistics
Faculty of Natural Sciences