Abstract
We study convergence and convergence rates for resampling schemes in Sequential Monte Carlo (SMC) methods. Our primary contributions include a general consistency theorem based on the property of negative association (NA), which establishes the almost-sure weak convergence of Kitagawa’s stratified resampling. We introduce a new resampling algorithm based on the Srinivasan Sampling Process (SSP) that ensures negative association and order-invariance. Furthermore, we confirm that ordering particles via Hilbert curves in $\mathbb{R}^d$ achieves a variance of the resampling error at a rate of $\mathcal{O}(N^{-(1+1/d)})$, surpassing the standard $\mathcal{O}(N^{-1})$ rate.
Introduction
Sequential Monte Carlo (SMC) methods, or particle filters, represent probability distributions through a set of weighted particles. A recurring challenge in these methods is weight degeneracy, where a small number of particles eventually carry the majority of the total weight. Resampling is the standard solution, involving the replication of high-weight particles and the removal of low-weight ones to maintain a representative sample.
While multinomial resampling is theoretically straightforward, it introduces significant Monte Carlo noise. Practitioners often turn to stratified or systematic resampling for better empirical performance. However, systematic resampling lacks a rigorous proof of convergence and is sensitive to the input order of particles. This paper addresses these gaps by providing a unified framework for consistency and introducing more robust, faster-converging algorithms.
Negative Association and Consistency
The core theoretical contribution of this work centers on Negative Association (NA). A set of random variables is negatively associated if the probability of them being "large" simultaneously is lower than if they were independent. This property prevents the "clumping" of particles that leads to high variance.
The authors establish a General Consistency Theorem: any resampling scheme satisfying the NA property achieves almost-sure weak convergence. This framework allows for the first formal proof of convergence for Kitagawa’s stratified resampling. Conversely, the paper demonstrates that systematic resampling fails to satisfy NA, explaining its potential for instability and dependence on particle ordering.
The SSP Resampling Algorithm
To bridge the gap between the low variance of systematic resampling and the theoretical reliability of stratified resampling, the authors introduce SSP Resampling. Based on the Srinivasan Sampling Process—a stochastic rounding technique—this algorithm satisfies the NA property.
Unlike systematic resampling, SSP is order-invariant. It provides the same statistical guarantees regardless of how the input particles are sorted, making it a more robust choice for complex filtering tasks. SSP maintains a computational complexity of $\mathcal{O}(N)$, ensuring it remains a practical drop-in replacement for existing methods.
Hilbert Curve Ordering
In one-dimensional state spaces, sorting particles by their value before resampling is a known technique to reduce variance. The authors extend this to higher dimensions ($d > 1$) by utilizing Hilbert space-filling curves.
By mapping multi-dimensional particle states onto a 1D line while preserving local spatial relationships, the Hilbert curve allows the resampling process to maintain spatial "stratification." The authors prove that for Hilbert-ordered stratified resampling, the variance of the resampling error is $\mathcal{O}(N^{-(1+1/d)})$. This is a significant improvement over the standard $\mathcal{O}(N^{-1})$ rate, particularly in low-to-moderate dimensions.
Results and Discussion
The theoretical findings are supported by numerical experiments using synthetic linear Gaussian state-space models. Over 500 time steps with $N = 2^{13}$ particles, the results indicate:
- Superiority of SSP: SSP resampling generally outperforms standard stratified resampling, particularly when paired with guided proposals.
- Convergence Rates: The predicted $\mathcal{O}(N^{-(1+1/d)})$ convergence rate for Hilbert-ordered schemes is empirically observed, confirming Kitagawa’s long-standing conjecture.
- Computational Trade-offs: While the resampling step remains $\mathcal{O}(N)$, the necessary sorting for Hilbert ordering introduces an $\mathcal{O}(N \log N)$ overhead.
Conclusion and Future Work
This research provides the theoretical foundation for advanced resampling techniques in SMC. By identifying Negative Association as the key to consistency and Hilbert curves as the path to faster convergence, the authors offer a roadmap for more efficient particle filters. Future work remains to be done in extremely high-dimensional spaces where the $1/d$ benefit diminishes, and in exploring the interaction between these resampling schemes and Auxiliary Particle Filters (APF).
Summary updated