Stratification and Optimal Resampling for Sequential Monte Carlo
Stratification and Optimal Resampling for Sequential Monte Carlo
复制标题
顺序蒙特卡罗的分层和最佳重采样
DOI：
10.1093/biomet/asab004
复制
发表时间：
2020-04
期刊：
影响因子：
2.7
通讯作者：
Jun S. Liu
中科院分区：
文献类型：
--
作者：
Yichao Li;Wenshuo Wang;Ke Deng;Jun S. Liu
顺序蒙特卡罗（SMC），也称为粒子滤波器，已被广泛接受为一种对动态系统进行推断的强大计算工具。SMC中的一个关键步骤是重采样，它起到引导算法朝着……的作用。
Sequential Monte Carlo (SMC), also known as particle filters, has been widely accepted as 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 the future dynamics. Several strategies have been proposed and used in practice, including multinomial resampling, residual resampling (Liu and Chen 1998), optimal resampling (Fearnhead and Clifford 2003), stratified resampling (Kitagawa 1996), and optimal transport resampling (Reich 2013). We show that, in the one dimensional case, optimal transport resampling is equivalent to stratified resampling on the sorted particles, and they both minimize the resampling variance as well as the expected squared energy distance between the original and resampled empirical distributions; in the multidimensional case, the variance of stratified resampling after sorting particles using Hilbert curve (Gerber et al. 2019) in $\mathbb{R}^d$ is $O(m^{-(1+2/d)})$, an improved rate compared to the original $O(m^{-(1+1/d)})$, where $m$ is the number of particles. This improved rate is the lowest for ordered stratified resampling schemes, as conjectured in Gerber et al. (2019). We also present an almost sure bound on the Wasserstein distance between the original and Hilbert-curve-resampled empirical distributions. In light of these theoretical results, we propose the stratified multiple-descendant growth (SMG) algorithm, which allows us to explore the sample space more efficiently compared to the standard i.i.d. multiple-descendant sampling-resampling approach as measured by the Wasserstein metric. Numerical evidence is provided to demonstrate the effectiveness of our proposed method.
登录
查看更多内容
DOI：
10.1046/j.1467-9884.2003.t01-6-00383_8.x
发表时间：
2003-12
期刊：
--
影响因子：
--
作者：
Freda Kemp
通讯作者：
Freda Kemp
DOI：
--
发表时间：
--
期刊：
--
影响因子：
--
作者：
Xiao-Li Hu;Thomas B. Schön;L. Ljung
通讯作者：
Xiao-Li Hu;Thomas B. Schön;L. Ljung
影响因子：
3.7
作者：
KONG, A;LIU, JS;WONG, WH
通讯作者：
WONG, WH
DOI：
10.1002/chin.199640314
发表时间：
1996-10
期刊：
ChemInform
影响因子：
--
作者：
S. Fahy
通讯作者：
S. Fahy
DOI：
10.1049/ip-rsn:19990255
发表时间：
1999-02-01
期刊：
IEE PROCEEDINGS-RADAR SONAR AND NAVIGATION
影响因子：
--
作者：
Carpenter, J;Clifford, P;Fearnhead, P
通讯作者：
Fearnhead, P