Toward Practical N2 Monte Carlo: the Marginal Particle Filter
This work addresses computational bottlenecks in sequential Monte Carlo methods for state estimation in non-linear, non-Gaussian models, offering practical improvements for applications like robotics and finance.
The authors tackled the computational inefficiency of particle filters by introducing the Marginal Particle Filter, which operates directly on the marginal distribution to avoid importance sampling in growing dimensions, achieving a reduction in variance and lowering the cost from O(N^2) to O(N log N).
Sequential Monte Carlo techniques are useful for state estimation in non-linear, non-Gaussian dynamic models. These methods allow us to approximate the joint posterior distribution using sequential importance sampling. In this framework, the dimension of the target distribution grows with each time step, thus it is necessary to introduce some resampling steps to ensure that the estimates provided by the algorithm have a reasonable variance. In many applications, we are only interested in the marginal filtering distribution which is defined on a space of fixed dimension. We present a Sequential Monte Carlo algorithm called the Marginal Particle Filter which operates directly on the marginal distribution, hence avoiding having to perform importance sampling on a space of growing dimension. Using this idea, we also derive an improved version of the auxiliary particle filter. We show theoretic and empirical results which demonstrate a reduction in variance over conventional particle filtering, and present techniques for reducing the cost of the marginal particle filter with N particles from O(N2) to O(N logN).