We derive a new theory of Bayesian particle flow that bullet proofs the algorithm against stiffness. Many researchers have attempted to apply particle flow filters, but sometimes they have gotten disappointing results owing to stiffness. Such researchers may be experts in fancy estimation algorithms, but they are rarely experts in mitigating stiffness for Itô stochastic differential equations. We solve this problem by bullet-proofing the Bayesian particle flow algorithm itself against stiffness. The new theory allows us to avoid fancy stiff ODE solvers that require large amounts of computer run time, and which are not parallelizable on GPUs. We also derive a very simple upper bound on the stiffness for our Gromov particle flow that gives us insight into the root cause of the problem. This shows that the stiffness of the flow is infinite if we do not directly measure all components of the state vector. The new theory fixes this problem completely. This paper is for normal engineers who do not have Itô calculus for breakfast.
We have invented two new Bayesian deep learning algorithms using stochastic particle flow to compute Bayes’ rule. These learning algorithms have a continuum of layers, in contrast with 10 to 100 discrete layers in standard deep learning neural nets. We compute Bayes’ rule for learning using a stochastic particle flow designed with Gromov’s method. Both deep learning and standard particle filters suffer from the curse of dimensionality, and we mitigate this problem by using stochastic particle flow to compute Bayes’ rule. The intuitive explanation for the dramatic reduction in computational complexity is that stochastic particle flow adaptively moves particles to the correct region of d dimensional space to represent the multivariate probability density of the state vector conditioned on the data. There is nothing analogous to this in standard neural nets (deep or shallow), where the geometry of the network is fixed.
We show the results of numerical experiments for a new algorithm for stochastic particle flow filters designed
using Gromov’s method. We derive a simple exact formula for Q in certain special cases. The purpose of using stochastic
particle flow is two fold: improve estimation accuracy of the state vector and improve the accuracy of uncertainty
quantification. Q is the covariance matrix of the diffusion for particle flow corresponding to Bayes’ rule.
We describe a new algorithm for stochastic particle flow filters using Gromov’s method. We derive a simple
exact formula for Q in certain special cases. The purpose of using stochastic particle flow is two fold: improve estimation
accuracy of the state vector and improve the accuracy of uncertainty quantification. Q is the covariance matrix of the
diffusion for particle flow corresponding to Bayes’ rule.
In a recent paper by Mallick and Sindhu, they assert three “problems” with our particle flow theory for Bayes’ rule. Our paper explains why all three assertions are wrong.
We show numerical results for a new nonlinear filtering algorithm that is analogous to Coulomb's law. We have
invented a new theory of exact particle flow for nonlinear filters. The flow of particles corresponding to Bayes' rule is
computed from the gradient of the solution of Poisson's equation, and it is analogous to Coulomb's law. Our theory is a
radical departure from other particle filters in several ways: (1) we compute Bayes' rule using a flow of particles rather
than as a pointwise multiplication; (2) we never resample particles; (3) we do not use a proposal density; (4) we do not
use importance sampling or any other MCMC algorithm; and (5) our filter is roughly 6 to 8 orders of magnitude faster
than standard particle filters for the same accuracy.
We have invented a new theory of exact particle flow for nonlinear filters. The flow of particles corresponding to Bayes'
rule is computed from the gradient of the solution of Poisson's equation, and it is analogous to Coulomb's law. Our
theory is a radical departure from other particle filters in several ways: (1) we compute Bayes' rule using a flow of
particles rather than as a pointwise multiplication; (2) we never resample particles; (3) we do not use a proposal density;
(4) we do not use importance sampling or any other MCMC algorithm; and (5) our filter is roughly 6 to 8 orders of
magnitude faster than standard particle filters for the same accuracy.
KEYWORDS: Particles, Particle filters, Nonlinear filtering, Probability theory, Filtering (signal processing), Monte Carlo methods, Fluid dynamics, Palladium, Diffusion, Computing systems
We have invented a new theory of exact particle flow for nonlinear filters. This
generalizes our theory of particle flow that is already many orders of magnitude faster than
standard particle filters and which is several orders of magnitude more accurate than the
extended Kalman filter for difficult nonlinear problems. The new theory generalizes our recent
log-homotopy particle flow filters in three ways: (1) the particle flow corresponds to the exact flow
of the conditional probability density; (2) roughly speaking, the old theory was based on
incompressible flow (like subsonic flight in air), whereas the new theory allows compressible flow
(like supersonic flight in air); (3) the old theory suffers from obstruction of particle flow as well as
singularities in the equations for flow, whereas the new theory has no obstructions and no
singularities. Moreover, our basic filter theory is a radical departure from all other particle filters in
three ways: (a) we do not use any proposal density; (b) we never resample; and (c) we compute
Bayes' rule by particle flow rather than as a point wise multiplication.
We study 17 distinct methods to approximate the gradient of the log-homotopy for nonlinear filters.
This is a challenging problem because the data are given as function values at random points in high
dimensional space. This general problem is important in optimization, financial engineering,
quantum chemistry, chemistry, physics and engineering. The best general method that we have
developed so far uses a simple idea borrowed from geology combined with a fast approximate k-NN
algorithm. Extensive numerical experiments for five classes of problems shows that we get
excellent performance.
Contrary to assertions in the literature, we show that the Extended Kalman Filter (EKF) is superior to the Unscented Kalman Filter (UKF) for certain nonlinear estimation problems. In particular, for nonlinearities that are odd functions of the state vector (e.g., x3) the Unscented Kalman Filter usually performs well, whereas for even nonlinearities (e.g., x2), the Extended Kalman Filter is sometimes much better than the Unscented Kalman Filter. This is contrary to the usual engineering folklore, and therefore we have checked our results very thoroughly. In particular, the Unscented Kalman Filter correctly approximates the conditional mean using a 4th order Gauss-Hermite quadrature, in contrast to the Extended Kalman Filter which uses a simple 0th order approximation, but the conditional mean is not the desired estimate in practical applications for strongly bimodal conditional probability densities, which are induced by even nonlinearities, owing to a sign ambiguity. On the other hand, even nonlinearities do not always induce multimodal densities that persist for a significant amount of time, and thus the Unscented Kalman Filter sometimes performs well for such problems. We study the effects of initial uncertainty of the state vector and nonlinearity in measurements.
We discuss the problem associated with obtaining an image of an object from the magnitude of its Fourier transform. This problem arises in many imaging applications. We discuss some new ideas developed to address this problem and describe constraints on the object function that can lead to its Fourier transform having only real zeros, thereby eliminating the phase retrieval problem.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.