Comparison of resampling schemes for particle filtering

By Randal Douc, Olivier Capp'e, Eric Moulines. 2005

1,050 citations recorded by the source corpus.

This contribution is devoted to the comparison of various resampling approaches that have been proposed in the literature on particle filtering. It is first shown using simple arguments that the so-called residual and stratified methods do yield an improvement over the basic multinomial resampling approach. A simple counter-example showing that this property does not hold true for systematic resampling is given. Finally, some results on the large-sample behavior of the simple bootstrap filter algorithm are given. In particular, a central limit theorem is established for the case where resampling is performed using the residual approach.

Subfields: Artificial Intelligence, Civil and Structural Engineering, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Civil and Structural Engineering

In Computer Networks and Communications

Citations in the corpus

Kernel Sequential Monte Carlo (2015, methodology): “Static SMC then applies re-sampling, constructing an equally-weighted set of particles X̃t = {X̃ t}i=1 by sampling with replacement from Xt−1 with weights proportional to W̃ i t , [7].”
An Overview of Existing Methods and Recent Advances in Sequential Monte Carlo (2007, background): “Some of these alternative sampling schemes guarantee a reduced Monte Carlo variance, at a comparable computational cost [30], [31], [32], [33].”
Inference Networks for Sequential Monte Carlo in Graphical Models (2016, background): “,W n−1) corresponding to any standard resampling scheme (Douc et al., 2005).”
The Cardinality Balanced Multi-Target Multi-Bernoulli Filter and Its Implementations (2009, background): “Note that there are many resampling schemes available, and that the choice of resampling scheme affects the computational load as well as the Monte Carlo approximation error [21], [22].”
Intelligent Particle Filter and Its Application to Fault Detection of Nonlinear System (2015, background): “During the past decades, many resampling techniques have been constructed, and a review about these techniques can be found in [21].”
Dynamic Trees for Learning and Design (2009, background): “ces f(i)gN i=1 with predictive probability weight p((i) = i) /p(ytjxt;[T;S] (i) t )1) = p(ytjxt;S (i) t(xt ); as in (7), (10), or (13). There are various low-variance options for resampling (e.g., Cappe et al., 2005), and our implementation makes use of residual-resampling.´ Set T(i) t 1 = T (i) t 1”
Asynchronous Anytime Sequential Monte Carlo (2014, background): “Many different schemes for resampling particles exist; see [6] for an overview.”
Statistical Inference for Partially Observed Markov Processes via the R Package pomp (2015, methodology): “As pointed out by (Douc et al. 2005), stratified resampling performs better than multinomial sampling and Algorithm 2 is in practice comparable in performance to stratified resampling and somewhat faster.”
Unsupervised Detection and Tracking of Arbitrary Objects with Dependent Dirichlet Process Mixtures (2012, methodology): “Resampling strategies such as those described in [28] and [21] can be used.”
Rethinking the Effective Sample Size (2018, methodology): “, in particle filtering and other iterative or adaptive IS-based methods [10, 29].”
Negative association, ordering and convergence of resampling methods (2017, background): “However, it is known (Douc et al., 2005) that the variance of ρsyst(ζN )(ϕ) may not converge to 0 as N → +∞ (see also L’Ecuyer and Lemieux, 2000, for an explanation of this phenomenon).”
Gradient Importance Sampling (2015, background): “See [10] for a review including some theoretical results.”
Pedestrian localisation for indoor environments (2008, neutral): “Many resampling schemes have been proposed [83].”
A Tutorial on Particle Filtering and Smoothing: Fifteen years later (2008, methodology): “However, the systematic resampling algorithm introduced in [25] is the most widely-used algorithm in the literature as it is extremely easy to implement and outperforms other resampling schemes in most scenarios (although this is not guaranteed in general [13]).”
Data assimilation in the geosciences: An overview of methods, issues, and perspectives (2017, methodology): “Popular resampling schemes include multinomial resampling, residual resampling, and stochastic universal (or systematic) resampling, the latter minimizing the sampling noise introduced in the procedure (Douc & Cappé, 2005).”
Quantifying the uncertainty in change points (2012, methodology): “A comparison of resampling schemes is provided by Douc and Cappé (2005).”