Particle Filters for Tracking on Large Dimensional State Spaces with Frequently Multimodal Likelihoods (and Posteriors)

Papers (key idea)
Papers (applications) Software
Some Details
Other Papers

Important Papers

Short Abstract:
We study efficient importance sampling techniques for particle filtering (PF) when either (a) the observation likelihood (OL) is frequently multimodal or heavy-tailed, or (b) the state space dimension is large or both. When the OL is multimodal, but the state transition pdf (STP) is narrow enough, the optimal importance density  is usually unimodal. Under this assumption, many techniques have been proposed. But when the STP is broad, this assumption does not hold. We study how existing techniques can be generalized to situations where the optimal importance density is multimodal, but is unimodal conditioned on a part of the state vector. Sufficient conditions to test for the unimodality of this conditional posterior are derived. Our result is directly extendable to testing for unimodality of any posterior.
    The number of particles, N, to accurately track using a PF increases with state space dimension, thus making any regular PF impractical for large dimensional tracking problems. But in most such problems, most of the state change occurs in only a few dimensions, while the change in the rest of the dimensions is small. We propose to replace importance sampling from a large part of the state space (whose conditional posterior is narrow enough) by just tracking the mode of the conditional posterior. This introduces some extra error, but it also greatly reduces the importance sampling dimension. The net effect is much smaller error for a given N, especially when the available N is small. %that a much smaller N suffices for a given error.
    An important class of large dimensional problems with multimodal OL is tracking spatially varying physical quantities such as temperature or pressure in a large area using a network of sensors which may be nonlinear and/or may have non-negligible failure probabilities. Improved performance of our proposed algorithms over existing PFs is demonstrated for this problem.

Some Details
Tracking is the problem of causally estimating a hidden sequence of vectors, called states, from a sequence of observations that may be noisy and nonlinear functions of the state. We are developing practically implementable particle filtering algorithms for tracking on large dimensional state spaces. Some examples of important large dimensional problems are: (i) tracking the boundary contour of a moving/deforming object or region-of-interest from image sequences, e.g. the boundary of a brain tumor in sequential MRI slices or of the beating heart; (ii) tracking spatially varying physical quantities, e.g. temperature or pressure, using measurements from a network of sensors; or (iii) time-varying input-output transfer function estimation, e.g. neuronal response estimation.
    In many real applications, the observation likelihood (OL) may be heavy tailed (e.g. due to outliers) or multimodal, for e.g. when there are two different types of sensors tracking temperature at one location, each with some probability of failure. The number of possible modes becomes very large when tracking temperature at all sensor nodes. In contour tracking, multiple OL modes occur due to cluttering objects in the background or foreground (partial occlusions) or due to low contrast imagery. These are examples of situations where particle filtering is really required (EKF, UKF, PMT etc will not work). Direct application of particle filters for large dimensional problems is impractical, due to the reduction in effective particle size as dimension increases. But, in most large dimensional systems, at any given time, “most of the state change” occurs in a small number of dimensions (“effective basis”) while the change in the rest of the state space (“residual space”) is “small”. The effective basis can be time varying. This idea forms the basis of our work.
    Under certain assumptions that imply narrowness of the state transition prior, many efficient importance sampling techniques have been proposed in literature. For large dimensional state spaces (LDSS), these assumptions may not always hold. But, it is usually true that at a given time, state change in all except a few dimensions is small. We use this fact to design a simple modification (called PF-EIS) of an existing importance sampling technique. Also, importance sampling on an LDSS is expensive (requires large number of particles, N) even with the best technique. But if the “residual space” variance is small enough, we can replace importance sampling in residual space by posterior Mode Tracking (MT). We call this idea PF-MT. MT is a deterministic step and hence this drastically reduces the importance sampling dimension for LDSS (from the LDSS dimension to the effective basis dimension), hence greatly reducing the required N. Of course, the error in the estimate of the residual state will also increase. But for 200-250 dim problems (e.g. contour tracking or tracking temperature in a wide area with large number of sensors) being tracked with only a small number of particles (e.g. N=50,100), this error is more than offset by the reduction in error due to improved effective particle size. Note that PF-MT can also be understood as an approximate Rao-Blackwellization technique that only requires the posterior of the residual space to be unimodal.


Particle filtering for large dimensional and multimodal problems Invited talk at the Opening Workshop for the SAMSI program on Sequential Monte Carlo Methods (September 2008)
Tracking (Optimal Filtering) on Large Dimensional State Spaces,   UCLA EE dept (May'07) & UCSD ECE dept (Dec'06)
Deformable Contour Tracking,  Invited talks at SAMSI workshop on Geometry and Statistics of Shape Spaces (July'07),  IPAM workshop on Random Shapes for Image Processing (May'07), Univ of Iowa (March'07), IMA Shape Spaces workshop (March'06)

Other Papers