Can local particle filters beat the curse of dimensionality?

Abstract

The discovery of particle filtering methods has enabled the use of nonlinear filtering in a wide array of applications. Unfortunately, the approximation error of particle filters typically grows exponentially in the dimension of the underlying model. This phenomenon has rendered particle filters of limited use in complex data assimilation problems. In this paper, we argue that it is often possible, at least in principle, to develop local particle filtering algorithms whose approximation error is dimension-free. The key to such developments is the decay of correlations property, which is a spatial counterpart of the much better understood stability property of nonlinear filters. For the simplest possible algorithm of this type, our results provide under suitable assumptions an approximation error bound that is uniform both in time and in the model dimension. More broadly, our results provide a framework for the investigation of filtering problems and algorithms in high dimension.

arXiv commentPublished at http://dx.doi.org/10.1214/14-AAP1061 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Sharp failure rates for the bootstrap particle filter in high dimensions
• Evaluating Data Assimilation Algorithms
• Error Bounds and Normalizing Constants for Sequential Monte Carlo in High Dimensions
• Conditional ergodicity in infinite dimension
• Comparison Theorems for Gibbs Measures
• Phase Transitions in Nonlinear Filtering

Cited by in corpus (50)

• Fighting Sample Degeneracy and Impoverishment in Particle Filters: A Review of Intelligent Approaches
• Data Assimilation: A Mathematical Introduction
• Three discussions of the paper "sequential quasi-Monte Carlo sampling", by M. Gerber and N. Chopin
• Particle Filters and Data Assimilation
• Particle Filtering with Invertible Particle Flow
• Langevin and Hamiltonian based Sequential MCMC for Efficient Bayesian Filtering in High-dimensional Spaces
• Deterministic Mean-field Ensemble Kalman Filtering
• Multilevel Sequential${}^2$ Monte Carlo for Bayesian Inverse Problems
• On the Stability of Kalman-Bucy Diffusion Processes
• Probabilistic learning of nonlinear dynamical systems using sequential Monte Carlo
• Divide-and-Conquer with Sequential Monte Carlo
• A hybrid particle-ensemble Kalman filter for problems with medium nonlinearity
• Nested Sequential Monte Carlo Methods
• Nonlinear System Identification: Learning while respecting physical models using a sequential Monte Carlo method
• A comparison of nonlinear extensions to the ensemble Kalman filter: Gaussian Anamorphosis and Two-Step Ensemble Filters
• A local ensemble transform Kalman particle filter for convective scale data assimilation
• Invertible Particle Flow-based Sequential MCMC with extension to Gaussian Mixture noise models
• A generic map from non-Lindblad to Lindblad master equations
• On the Mathematical Theory of Ensemble (Linear-Gaussian) Kalman-Bucy Filtering
• Performance analysis of local ensemble Kalman filter
• Approximate Smoothing and Parameter Estimation in High-Dimensional State-Space Models
• Perturbations and projections of Kalman-Bucy semigroups
• Grid Based Nonlinear Filtering Revisited: Recursive Estimation & Asymptotic Optimality
• Ensemble Kalman Inversion for General Likelihoods
• A McKean optimal transportation perspective on Feynman-Kac formulae with application to data assimilation
• Bagged filters for partially observed interacting systems
• Importance Sampling: Intrinsic Dimension and Computational Cost
• Informing policy via dynamic models: Cholera in Haiti
• Asymptotically Optimal Discrete Time Nonlinear Filters From Stochastically Convergent State Process Approximations
• 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
• Improving particle filter performance by smoothing observations
• Improving the particle filter in high dimensions using conjugate artificial process noise
• State Space Model based Trust Evaluation over Wireless Sensor Networks: An Iterative Particle Filter Approach
• Phase Transitions in Nonlinear Filtering
• Bayesian Update with Importance Sampling: Required Sample Size
• Sequential Channel State Tracking & SpatioTemporal Channel Prediction in Mobile Wireless Sensor Networks
• A State-Space Perspective on Modelling and Inference for Online Skill Rating
• Stein particle filtering
• Adaptive particle-based approximations of the Gibbs posterior for inverse problems
• Adaptively Blocked Particle Filtering with Spatial Smoothing in Large-Scale Dynamic Random Fields
• Sequential Monte Carlo Methods for High-Dimensional Inverse Problems: A case study for the Navier-Stokes equations
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning
• Predictive Learning on Hidden Tree-Structured Ising Models
• Hidden Markov Neural Networks
• Long-time Asymptotics of the Filtering Distribution for Partially Observed Chaotic Dynamical Systems
• Reducing the Bias in Blocked Particle Filtering for High-Dimensional Systems
• Optimal Transportation Methods in Nonlinear Filtering: The feedback particle filter
• Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities