|
Abstract:
|
Sequential Monte Carlo (SMC), also known as particle filters, is a powerful computational tool for making inference with dynamical systems. A key step in SMC is resampling, which plays the role of steering the algorithm towards future dynamics. We show that in one dimension, optimal transport resampling is equivalent to stratified resampling on sorted particles, and they both minimize the resampling variance and the expected squared energy distance; in the multidimensional case, the variance of stratified resampling after sorting particles with Hilbert curve (Gerber et al. 2019) in R^d is O(1/m^(1+2/d)), improving the original O(1/m^(1+1/d)), where m is number of particles. This improved rate is the lowest for ordered stratified resampling schemes as originally conjectured. We also present a bound on the Wasserstein distance between the original and Hilbert-curve-resampled empirical distributions. In light of these results, we propose the stratified multiple-descendant growth (SMG) algorithm, which allows us to explore the sample space more efficiently compared to the i.i.d. multiple-descendant approach. We provide theory and numerical evidence to demonstrate SMG's effectiveness.
|
