Diffusion map-based algorithm for gain function approximation in the feedback particle filter

Feedback particle filter (FPF) is a numerical algorithm to approximate the solution of the nonlinear filtering problem in continuous-time settings. In any numerical implementation of the FPF algorithm, the main challenge is to numerically approximate the so-called gain function. A numerical algorithm for gain function approximation is the subject of this paper. 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 finitely many particles sampled from the probability distribution ρ. A diffusion map-based algorithm was proposed by the authors in prior works [A. Taghvaei and P. G. Mehta, Gain function approximation in the feedback particle filter, in 2016 IEEE 55th Conference on Decision and Control (CDC), IEEE, 2016, pp. 5446-5452], [A. Taghvaei, P. G. Mehta, and S. P. Meyn, Error estimates for the kernel gain function approximation in the feedback particle filter, in American Control Conference (ACC), IEEE, 2017, pp. 4576-4582] to solve this problem. The algorithm is named as such because it involves, as an intermediate step, a diffusion map approximation of the exact semigroup e^Δρ. The original contribution of this paper is to carry out a rigorous error analysis of the diffusion map-based algorithm. The error is shown to include two components: bias and variance. The bias results from the diffusion map approximation of the exact semigroup. The variance arises because of finite sample size. Scalings and upper bounds are derived for bias and variance. These bounds are then illustrated with numerical experiments that serve to emphasize the effects of problem dimension and sample size. The proposed algorithm is applied to two filtering examples and comparisons provided with the sequential importance resampling (SIR) particle filter.