Share Email Print

Proceedings Paper

Mysterious computational complexity of particle filters
Author(s): Frederick E. Daum; Jim Huang
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 7 August 2002
PDF: 9 pages
Proc. SPIE 4728, Signal and Data Processing of Small Targets 2002, (7 August 2002); doi: 10.1117/12.478522
Show Author Affiliations
Frederick E. Daum, Raytheon Electronic Systems (United States)
Jim Huang, Raytheon Electronic Systems (United States)

Published in SPIE Proceedings Vol. 4728:
Signal and Data Processing of Small Targets 2002
Oliver E. Drummond, Editor(s)

© SPIE. Terms of Use
Back to Top