7 August 2002 Mysterious computational complexity of particle filters
Author Affiliations +
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.
© (2002) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Frederick E. Daum, Frederick E. Daum, Jim Huang, Jim Huang, "Mysterious computational complexity of particle filters", Proc. SPIE 4728, Signal and Data Processing of Small Targets 2002, (7 August 2002); doi: 10.1117/12.478522; https://doi.org/10.1117/12.478522

Back to Top