Curse-of-dimensionality revisited: Collapse of the particle filter in very large scale systems

By Thomas Bengtsson, Peter J. Bickel, Bo Li. 2008

454 citations recorded by the source corpus.

It has been widely realized that Monte Carlo methods (approximation via a sample ensemble) may fail in large scale systems. This work offers some theoretical insight into this phenomenon in the context of the particle filter. We demonstrate that the maximum of the weights associated with the sample ensemble converges to one as both the sample size and the system dimension tends to infinity. Specifically, under fairly weak assumptions, if the ensemble size grows sub-exponentially in the cube root of the system dimension, the convergence holds for a single update step in state-space models with independent and identically distributed kernels. Further, in an important special case, more refined arguments show (and our simulations suggest) that the convergence to unity occurs unless the ensemble grows super-exponentially in the system dimension. The weight singularity is also established in models with more general multivariate likelihoods, e.g. Gaussian and Cauchy. Although presented in the context of atmospheric data assimilation for numerical weather prediction, our results are generally valid for high-dimensional particle filters.

Subfields: Atmospheric Science, Environmental Engineering, Global and Planetary Change

View Paper: https://www.semanticscholar.org/paper/eca8b8be669508bf90e17a9aeda5cc81cbced8e1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atmospheric Science

In Environmental Engineering

In Global and Planetary Change

Citations in the corpus

Obstacles to High-Dimensional Particle Filtering (2008, methodology): “The goal of our study is to describe the situations in which collapse occurs, both through the rigorous asymptotic results of Bengtsson et al. (2008) for large N y and N e and through simulations informed by the as-ymptotics.”
A Localized Particle Filter for High-Dimensional Nonlinear Systems (2016, background): “Under weak assumptions, Bengtsson et al. (2008) prove that filter degeneracy occurs when Ne increases subexponentially with the state dimension.”
On the stability of sequential Monte Carlo methods in high dimensions (2011, methodology): “The articles [4, 6, 13, 48] have considered some problems in this direction.”
Error Bounds and Normalising Constants for Sequential Monte Carlo Samplers in High Dimensions (2014, background): “Recently (see [2], [4], and [24]) it was shown that some IS methods do not stabilise, in an appropriate sense, as the dimension of target densities in a particular class grows, unless N grows exponentially fast with dimension d.”