Design and analysis of particle-based algorithms for nonlinear filtering and sampling

Taghvaei, Amirhossein

Permalink

https://hdl.handle.net/2142/105673 Copy

Description

Title

Design and analysis of particle-based algorithms for nonlinear filtering and sampling

Author(s)

Taghvaei, Amirhossein

Issue Date

2019-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Mehta, Prashant

Doctoral Committee Chair(s)

Mehta, Prashant

Committee Member(s)

• Hajek, Bruce
• Laugesen, Richard
• Raginsky, Maxim

Department of Study

Mechanical Sci & Engineering

Discipline

Mechanical Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Nonlinear filtering
• Monte-Carlo methods
• Mean-field optimal control
• Optimal transportation

Abstract

This thesis is concerned with the design and analysis of particle-based algorithms for two problems: (i) the nonlinear filtering problem; (ii) and the problem of sampling from a target distribution. The contributions for these two problems appear in Part I and Part~II of the thesis. For the nonlinear filtering problem, the focus is on the feedback particle filter (FPF) algorithm. In the FPF algorithm, the empirical distribution of the particles is used to approximate the posterior distribution of the nonlinear filter. The particle update is implemented using a feedback control law that is designed such that the distribution of the particles, in the mean-field limit, is exactly equal to the posterior distribution. In Part I of this thesis, three separate problems related to the FPF methodology and algorithm are addressed. The first problem, addressed in Chapter 2 of the thesis, is concerned with gain function approximation in the FPF algorithm. The exact gain function is the solution of a Poisson equation involving a probability-weighted Laplacian. The numerical problem is to approximate this solution using only particles sampled from the probability distribution. A diffusion map-based algorithm is presented for this problem. The algorithm is based on a reformulation of the Poisson equation as a fixed-point equation that involves the diffusion semigroup corresponding to the weighted Laplacian. The fixed-point problem is approximated with a finite-dimensional problem in two steps: In the first step, the semigroup is approximated with a Markov operator referred to as diffusion map. In the second step, the diffusion map is approximated empirically, using particles, as a Markov matrix. A procedure for carrying out error analysis of the approximation is introduced and certain asymptotic estimates for bias and variance error are derived. Some comparative numerical experiments are performed for a problem with non-Gaussian distribution. The algorithm is applied and illustrated for a numerical filtering example. As part of the error analysis, some new results about the diffusion map approximation are obtained. These include (i) new error estimates between the diffusion map and the exact semigroup, based on the Feynman-Kac representation of the semigroup; (ii) a spectral gap for the diffusion map, based on the Foster-Lyapunov function method from the theory of stability of Markov processes; (ii) and error estimates for the empirical approximation of the diffusion map. The second problem, addressed in Chapter 3 of the thesis, is motivated by the so-called uniqueness issue of FPF control law. The control law in FPF is designed such that the distribution of the particles, in the mean-field limit, is exactly equal to the posterior distribution. However, it has been noted in the literature that the FPF control law is not unique. The objective of this research is to describe a systematic approach to obtain a unique control law for FPF. In Chapter 3, the optimality criteria from optimal transportation theory is used to identify a unique control law for FPF, in the linear Gaussian setting. Two approaches are outlined. The first approach is based on a time-stepping optimization procedure. We consider a time discretization of the problem, construct a discrete-time stochastic process by composition of sequence of optimal transport maps between the posterior distributions of two consecutive time instants, and then take the limit as the time step-size goes to zero. We obtain explicit formula for the resulting control law in the linear Gaussian setting. The control law is deterministic and requires the covariance matrix of the resulting stochastic process to be invertible. We present an alternative approach, which allows for singular covariance matrices. The resulting control law has additional stochastic terms, which vanish when the covariance matrix is non-singular. The second construction is important for finite-N implementation of the algorithm, where the empirical covariance matrix might be singular. The third problem, addressed in Chapter 4, is concerned with the convergence and the error analysis for FPF algorithm. It is known that in the mean-field limit, the distribution of the particles is equal to the posterior distribution. However little is known about the convergence of the finite-N algorithm to the mean-field limit. We consider the linear Gaussian setting, and study two types of FPF algorithm: The deterministic linear FPF and the stochastic linear FPF. The important question in the linear Gaussian setting is about convergence of the empirical mean and covariance of the particles to the exact mean and covariance given by the Kalman filter. We derive equations for the evolution of empirical mean and covariance for the finite-N system for both algorithms. Remarkably, for the deterministic linear FPF, the equations for the mean and variance are identical to the Kalman filter. This allows strong conclusions on convergence and error properties under the assumption that the linear system is controllable and observable. It is shown that the error converges to zero even with finite number of particles. For the stochastic linear FPF, the equations for the empirical mean and covariance involve additional stochastic terms. Error estimates are obtained for the empirical mean and covariance under the stronger assumption that the linear system is stable and fully observable. We also presents propagation of chaos error analysis for both algorithms. The Part 2 of the thesis is concerned with the sampling problem, where the objective is to sample from a unnormalized target probability distribution. The problem is formulated as an optimization problem on the space of probability distributions, where the objective is to minimize the relative entropy with respect to the target distribution. The gradient flow with respect to the Riemannian metric induced by the Wasserstein distance, is known to lead to Markov Chain Monte-Carlo (MCMC) algorithms based on the Langevin equation. The main contribution is to present a methodology and numerical algorithms for constructing accelerated gradient flows on the space of probability distributions. In particular, the recent variational formulation of accelerated methods in (Wibinoso et al., 2016) is extended from vector valued variables to probability distributions. The variational problem is modeled as a mean-field optimal control problem. The maximum principle of optimal control theory is used to derive Hamilton's equations for the optimal gradient flow. A quantitative estimate on the asymptotic convergence rate is provided based on a Lyapunov function construction, when the objective functional is displacement convex. Two numerical approximations are presented to implement the Hamilton's equations as a system of N interacting particles. The algorithm is numerically illustrated and compared with the MCMC and Hamiltonian MCMC algorithms.

Graduation Semester

2019-08

Type of Resource

text

Permalink

http://hdl.handle.net/2142/105673

Copyright and License Information

Copyright 2019 Amirhossein Taghvaei

Owning Collections