Generalized Particle Flow for Maximal Stability of Nonlinear Filters

Abstract We derive a new particle flow to maximize the stability of nonlinear filters. This greatly improves the performance of such filters for unstable plants, as well as stable plants with slow mixing (due to low process noise and/or eigenvalues that are marginally stable). In particular, particle filters are generally not stable for unstable plants, in contrast with the Kalman filter, which is guaranteed to be stable under very mild conditions (e.g., controllability and observability of the system model), as proven in Kalman’s beautiful paper (1963). That is, the Kalman filter is stable despite the instability of the plant model. Recent attempts to understand the lack of stability for particle filters for unstable plants are surveyed by Ramon van Handel (SIAM Conference July 2009). This is a very serious practical problem, because the standard plant models for many applications are conditionally unstable. Moreover, the estimation accuracy of particle filters is generally a very strong function of the mixing of the plant model.

Numerical results show that our filter is many orders of magnuitude faster than the classic particle filter, and it is typically several orders of magnitude more accurate than the EKF for difficult nonlinear problems, including multimodal densities, quadratic & cubic nonlinearities, for fully coupled smooth problems with dimension (of the state vector) up to 24.

The key idea is to compute Bayes’ rule using a flow of particles rather than as a pointwise multiplication. This is analogous to the flow of particles used to model the dynamics of the system in standard particle filters. We do not have to use any proposal density or resampling, because we move the particles to the correct distribution in state space using our particle flow. This is a radical departure from other particle filters. The differential equation for classic particle flow (Daum & Huang SPIE Conference 2007) was derived using Liouville’s criterion, borrowed from physics. Other ingredients include: the chain rule, the Moore-Penrose inverse and a log-homotopy. It turns out that a homotopy does not work at all, owing to the singularity of the resulting ODE, but a log-homotopy removes the singularity and works extremely well. The most interesting and challenging part of this filter is the approximation of the gradient of the log-homotopy; we studied 17 distinct methods for this, and we now use a simple but effective approach borrowed from geology, combined with a fast approximate k-NN algorithm. This talk is for normal engineers, who do not have log-homotopy for breakfast.

• Lecture or concert series: Electrical Engineering Systems Seminar Series
• For further information: contact Shirley Slattery shirley@systems.caltech.edu phone: 626-395-4715