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.

arXiv commentPublished 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 (55)

• Fighting Sample Degeneracy and Impoverishment in Particle Filters: A Review of Intelligent Approaches
• Data Assimilation: A Mathematical Introduction
• Particle Kalman Filtering: A Nonlinear Bayesian Framework for Ensemble Kalman Filters
• Sequential Monte Carlo Methods for State and Parameter Estimation in Abruptly Changing Environments
• Identifying nonlinear dynamical systems via generative recurrent neural networks with applications to fMRI
• Particle Filters and Data Assimilation
• Particle Filtering with Invertible Particle Flow
• A population Monte Carlo scheme with transformed weights and its application to stochastic kinetic models
• Data Assimilation: The Schrödinger Perspective
• Sketch and Validate for Big Data Clustering
• Scaled unscented transform Gaussian sum filter: theory and application
• Conditions for successful data assimilation
• A hybrid particle-ensemble Kalman filter for problems with medium nonlinearity
• Robust Covariance Adaptation in Adaptive Importance Sampling
• Message Passing-Based 9-D Cooperative Localization and Navigation with Embedded Particle Flow
• Panel data analysis via mechanistic models
• Bayesian analysis of traffic flow on interstate I-55: The LWR model
• A comparison of nonlinear extensions to the ensemble Kalman filter: Gaussian Anamorphosis and Two-Step Ensemble Filters
• Invertible Particle Flow-based Sequential MCMC with extension to Gaussian Mixture noise models
• Parameter estimation by implicit sampling
• Approximate Smoothing and Parameter Estimation in High-Dimensional State-Space Models
• 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
• On the Stability of Sequential Monte Carlo Methods in High Dimensions
• Non-Asymptotic Analysis of Ensemble Kalman Updates: Effective Dimension and Localization
• A nonlinear population Monte Carlo scheme for the Bayesian estimation of parameters of $\alpha$-stable distributions
• Smoothing and parameter estimation by soft-adherence to governing equations
• A McKean optimal transportation perspective on Feynman-Kac formulae with application to data assimilation
• Grid Based Nonlinear Filtering Revisited: Recursive Estimation & Asymptotic Optimality
• Iterated Block Particle Filter for High-dimensional Parameter Learning: Beating the Curse of Dimensionality
• Bagged filters for partially observed interacting systems
• Multiple Bayesian Filtering as Message Passing
• Error Bounds and Normalizing Constants for Sequential Monte Carlo in High Dimensions
• Efficient particle filtering through residual nudging
• Randomized maximum likelihood based posterior sampling
• On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms
• Recursive Bayesian Filters for Data Assimilation
• Deep FPF: Gain function approximation in high-dimensional setting
• A scalable optimal-transport based local particle filter
• State Space Model based Trust Evaluation over Wireless Sensor Networks: An Iterative Particle Filter Approach
• Improving particle filter performance by smoothing observations
• A Bayesian inference and model selection algorithm with an optimisation scheme to infer the model noise power
• Kalman filtering and smoothing for linear wave equations with model error
• Bayesian Update with Importance Sampling: Required Sample Size
• Nearly Consistent Finite Particle Estimates in Streaming Importance Sampling
• Stein particle filtering
• Sequential Channel State Tracking & SpatioTemporal Channel Prediction in Mobile Wireless Sensor Networks
• A hybrid ensemble transform filter for nonlinear and spatially extended dynamical systems
• Particle Gaussian Mixture (PGM) Filters
• Sequential Markov Chain Monte Carlo for Bayesian Filtering with Massive Data
• Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff
• Nudging the particle filter
• Guided Unconditional and Conditional Generative Models for Super-Resolution and Inference of Quasi-Geostrophic Turbulence
• Iterated Gain-based Stochastic Filters for Dynamic System Identification: Annealing-type Iterations and the Filter Bank
• Optimal Transportation Methods in Nonlinear Filtering: The feedback particle filter