Paper Info
Title
How to Avoid the Curse of Dimensionality: Scalability of Particle Filters with and without Importance Weights.
Abstract
Particle filters are a popular and flexible class of numerical algorithms to solve a large class of nonlinear filtering problems. However, standard particle filters with importance weights have been shown to require a sample size that increases exponentially with the dimension D of the state space in order to achieve a certain performance, which precludes their use in very high-dimensional filtering problems. Here, we focus on the dynamic aspect of this "curse of dimensionality" (COD) in continuous-time filtering, which is caused by the degeneracy of importance weights over time. We show that the degeneracy occurs on a time scale that decreases with increasing D. In order to soften the effects of weight degeneracy, most particle filters use particle resampling and improved proposal functions for the particle motion. We explain why neither of the two can prevent the COD in general. In order to address this fundamental problem, we investigate an existing filtering algorithm based on optimal feedback control that sidesteps the use of importance weights. We use numerical experiments to show that this feedback particle filter (FPF) by [T. Yang, P. G. Mehta, and S. P. Meyn, IEEE Trans. Automat. Control, 58 (2013), pp. 2465-2480] does not exhibit a COD.
Year
DOI
Venue
2019
10.1137/17M1125340
SIAM REVIEW
Keywords
Field
DocType
particle filter,high-dimensional,filtering,sequential Monte Carlo
Mathematical optimization,Nonlinear filtering,Particle filter,Filter (signal processing),Curse of dimensionality,Mathematics,Scalability
Journal
Volume
Issue
ISSN
61
1
0036-1445
Citations 
PageRank 
References 
2
0.39
3
Authors
3
Name
Order
Citations
PageRank
Simone Carlo Surace120.39
Anna Kutschireiter220.39
Jean-pascal Pfister315013.64