Header

UZH-Logo

Maintenance Infos

How to avoid the curse of dimensionality: scalability of particle filters with and without importance weights


Surace, Simone Carlo; Kutschireiter, Anna; Pfister, Jean-Pascal (2017). How to avoid the curse of dimensionality: scalability of particle filters with and without importance weights. arXiv.org 1703.07879, Institute of Neuroinformatics.

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 Yang et al. (2013) does not exhibit a COD.

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 Yang et al. (2013) does not exhibit a COD.

Statistics

Downloads

0 downloads since deposited on 01 Mar 2018
0 downloads since 12 months

Additional indexing

Item Type:Working Paper
Communities & Collections:07 Faculty of Science > Institute of Neuroinformatics
Dewey Decimal Classification:570 Life sciences; biology
Language:English
Date:2017
Deposited On:01 Mar 2018 11:08
Last Modified:20 Mar 2018 00:42
Series Name:arXiv.org
ISSN:2331-8422
OA Status:Green
Free access at:Official URL. An embargo period may apply.
Official URL:https://arxiv.org/abs/1703.07879

Download

Download PDF  'How to avoid the curse of dimensionality: scalability of particle filters with and without importance weights'.
Preview
Content: Published Version
Filetype: PDF
Size: 499kB