Particle flow for nonlinear filters, Bayesian decisions and transport

16 October 2015
12:00 pm
Particle flow for nonlinear filters, Bayesian decisions and transport
Dr. Frederick Daum

We derive a new algorithm to compute Bayes’ rule for high dimensional problems, using particle flow rather than a point wise multiplication. The particle flow is induced by a log-homotopy of the conditional density from the prior to the posteriori. This algorithm is similar to Monge-Kantorovich transport, but it is much simpler and faster, because we do not use any optimality criteria. In particular, there is no relevant notion of physical effort to transport our particles. Consequently, we do not pick the flow to minimize a convex functional, and hence we avoid solving a variational problem. Moreover, we do not use resampling of particles or proposal densities or importance sampling or any Markov chain Monte Carlo method. But rather, we design the particle flow with the solution of a linear first order highly underdetermined PDE. We solve our PDE analytically as a formula, rather than using numerical methods, in order to reduce computational complexity. We have many methods to solve this PDE, but the best methods all avoid explicitly computing the normalizing constant of the conditional density. Our theory applies to smooth nowhere vanishing probability densities, and it is similar to Jürgen Moser’s coupling. We compare the new flow with state-of-the-art methods, including: Hamiltonian Monte Carlo, Metropolis- adjusted Langevin (MALA), regularized particle filters, auxiliary particle filters, etc. Our particle flow is many orders of magnitude faster than standard particle filters for the same accuracy. Furthermore, our filter beats the extended Kalman filter accuracy by several orders of magnitude for difficult nonlinear problems. The computational complexity for nonlinear filtering generally depends on: dimension of the state vector, degree of coupling between components of the state vector, stability of the plant, initial uncertainty of the state vector, measurement accuracy, shape of the conditional density (e.g., log-concave), Lipschitz constants of the log-densities, smoothness of the densities, and ill- conditioning of the Fisher information matrix. This talk describes a new particle flow that avoids normalization of the conditional density using an idea from quantum field theory (i.e., renormalization group flow), which results in a robust practical algorithm. Our PDE is linear with constant coefficients, and hence we can use the Fourier transform to solve it.