The Chopthin Algorithm for Resampling

DOI10.1109/TSP.2016.2558166zbMATH Open1414.94862DBLPjournals/tsp/GandyL16arXiv1502.07532OpenAlexW1541011473WikidataQ57834938 ScholiaQ57834938MaRDI QIDQ4620876FDOQ4620876

Authors: Axel Gandy, F. Din-Houn Lau 

Publication date: 8 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1502.07532

Recommendations

• An improving the residual resampling algorithm
• scientific article; zbMATH DE number 854595
• A simple resampling method by perturbing the minimand
• On general resampling algorithms and their performance in distribution estimation
• Adaptive resampling algorithms for estimating bootstrap distributions

Mathematics Subject Classification ID

Sampling theory in information and communication theory (94A20)

Cited In (1)

• Residual and stratified branching particle filters

Uses Software

• chopthin

This page was built for publication: The Chopthin Algorithm for Resampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620876)