Mysterious computational complexity of particle filters

Frederick E. Daum; Jim Huang

doi:10.1117/12.478522

7 August 2002 Mysterious computational complexity of particle filters

Frederick E. Daum, Jim Huang

Proceedings Volume 4728, Signal and Data Processing of Small Targets 2002; (2002) https://doi.org/10.1117/12.478522
Event: AeroSense 2002, 2002, Orlando, FL, United States

Abstract

Particle filtering (PF) is a relatively new method to solve the nonlinear filtering problem, which is very general and easy to code. The main issue with PF is the large computational complexity. In particular, for typical low dimensional tracking problems, the PF requires 2 to 4 orders of magnitude more computer throughput than the EKF, to achieve the same accuracy. It has been asserted that the PF avoids the curse of dimensionality, but there is no formula or theorem that bounds or approximates the computational complexity of the PF as a function of dimension (d). In this paper, we will derive a simple back-of-the-envelope formula that explains why a carefully designed PF should mitigate the curse of dimensionality for typical tracking problems, but that it does not avoid the curse of dimensionality in general. This new theory is related to the fact that the volume of the d dimensional unit sphere is an amazingly small fraction of the d dimensional unit cube, for large d.

Citation Download Citation

Frederick E. Daum and Jim Huang "Mysterious computational complexity of particle filters", Proc. SPIE 4728, Signal and Data Processing of Small Targets 2002, (7 August 2002); https://doi.org/10.1117/12.478522

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available