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

Abstract

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.

Published in at http://dx.doi.org/10.1214/193940307000000518 the IMS Collections (http://www.imstat.org/publications/imscollections.htm) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (22)

• Data Assimilation: A Mathematical Introduction
• Particle Filters and Data Assimilation
• A hybrid particle-ensemble Kalman filter for problems with medium nonlinearity
• Message Passing-Based 9-D Cooperative Localization and Navigation with Embedded Particle Flow
• A comparison of nonlinear extensions to the ensemble Kalman filter: Gaussian Anamorphosis and Two-Step Ensemble Filters
• Automatic maneuver detection and tracking of space objects in optical survey scenarios based on stochastic hybrid systems formulation
• Low-rank statistical finite elements for scalable model-data synthesis
• Non-Asymptotic Analysis of Ensemble Kalman Updates: Effective Dimension and Localization
• Bagged filters for partially observed interacting systems
• Iterated Block Particle Filter for High-dimensional Parameter Learning: Beating the Curse of Dimensionality
• Randomized maximum likelihood based posterior sampling
• On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms
• Deep FPF: Gain function approximation in high-dimensional setting
• A scalable optimal-transport based local particle filter
• A Bayesian inference and model selection algorithm with an optimisation scheme to infer the model noise power
• Bayesian Update with Importance Sampling: Required Sample Size
• Stein particle filtering
• Sequential Channel State Tracking & SpatioTemporal Channel Prediction in Mobile Wireless Sensor Networks
• Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff
• Iterated Gain-based Stochastic Filters for Dynamic System Identification: Annealing-type Iterations and the Filter Bank
• Guided Unconditional and Conditional Generative Models for Super-Resolution and Inference of Quasi-Geostrophic Turbulence
• Optimal Transportation Methods in Nonlinear Filtering: The feedback particle filter