On Particle Filters with High Complexity Combinatorial Likelihood Functions

Saddle point approximation methods are proposed for particle filters whose likelihood functions have high computational complexity due to combinatorial enumerations of the kind that arises in assignment problems, e.g., in multitarget, multisensor, and smoothing filters. Using techniques drawn from random matrix theory, it is shown that the computational complexity of the approximation depends on the cube of the number of measurements or the number of targets, whichever is smaller, for the class of probabilistic data association filters. The saddle point approximation method is also applicable to the class of stochastic flow filters.