|
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. In light of these results, we show that, for d>1, the mean square error of sequential quasi-Monte Carlo with n particles can be O(1/n^(1+4/[d(d+4)])) by implementing Hilbert curve resampling and selecting a specific low-discrepancy set. To the best of our knowledge, this is the first known convergence rate lower than o(1/n).
|
