Gain function approximation in the Feedback Particle Filter

Amirhossein Taghvaei, Prashant G. Mehta, Sean P. MeynarXiv 2019 · arXiv · OpenReview

Abstract

The Feedback Particle Filter (FPF) is a numerical algorithm designed to solve nonlinear filtering problems in continuous-time settings. A significant challenge in implementing FPF is the numerical approximation of the gain function, which is the solution to a Poisson equation involving a probability-weighted Laplacian $\Delta_\rho$. This paper analyzes a diffusion map-based algorithm that approximates this solution using a finite set of particles sampled from the distribution $\rho$. We provide a rigorous error analysis, decomposing the error into bias—arising from the diffusion map approximation of the exact semigroup—and variance—resulting from finite sample size. We derive scalings and upper bounds for these components and illustrate our findings through numerical experiments, comparing the FPF against the sequential importance resampling (SIR) filter.

Introduction

In nonlinear filtering, the objective is to estimate the hidden state of a dynamical system based on a stream of noisy observations. While the Kalman filter provides an optimal solution for linear Gaussian systems, real-world applications often involve nonlinear dynamics and non-Gaussian noise, necessitating more robust methods.

The Feedback Particle Filter (FPF) has emerged as a powerful alternative to traditional Sequential Importance Resampling (SIR) filters. Unlike SIR filters, which rely on reweighting particles—a process that often leads to "particle degeneracy" where only a few particles carry significant weight—the FPF utilizes a feedback control law to continuously move particles toward the posterior distribution. However, the implementation of this control law requires the calculation of a "gain function." This function is the solution to a complex partial differential equation (PDE) known as the Poisson equation. Solving this PDE in high-dimensional spaces using only a finite set of particles is the primary computational bottleneck in FPF applications.

The Diffusion Map-Based Algorithm

To address the challenge of gain function approximation, we utilize a diffusion map-based approach. The core strategy involves approximating the differential operators in the Poisson equation through local interactions between particles. The algorithm follows a four-step process:

  1. Semigroup Formulation: The Poisson equation is reformulated using the semigroup $e^{\Delta_\rho}$, which represents the heat equation acting on the particle distribution.
  2. Diffusion Map Approximation: The exact semigroup is approximated using a family of Markov operators $T_\epsilon$ based on a Gaussian kernel. For a sufficiently small bandwidth parameter $\epsilon$, these operators provide a close approximation of the continuous differential operator.
  3. Empirical Approximation: The continuous operators are replaced by an $N \times N$ Markov matrix $\mathbf{T}$, constructed directly from the $N$ particles in the system.
  4. Fixed-Point Iteration: The gain function is obtained by solving a finite-dimensional fixed-point equation: $\Phi = \mathbf{T}\Phi + \epsilon(\mathbf{h} - \pi(\mathbf{h}))$. This approach avoids the high cost of matrix inversions and scales computationally at $O(N^2)$.

Theoretical Error Analysis

The primary contribution of this work is a rigorous mathematical foundation for the error inherent in this approximation. Using Feynman-Kac representations and Foster-Lyapunov stability theory, we decompose the error into two distinct components:

  • Bias: This error results from the diffusion map's approximation of the exact semigroup. We demonstrate that the bias scales as $O(\epsilon)$.
  • Variance: This error arises from the finite sample size $N$. The variance is sensitive to the kernel bandwidth; as $\epsilon$ decreases to reduce bias, the variance increases because the approximation becomes more sensitive to the specific locations of the particles.

Our analysis yields a total error bound for the potential function $\phi$ of $O(\epsilon + \frac{1}{N^{1/2}\epsilon^{1+d/2}})$, where $d$ is the dimension of the state space. This highlights a fundamental bias-variance trade-off governed by the choice of $\epsilon$.

Numerical Experiments and Results

We evaluated the algorithm using several synthetic benchmarks designed to test its limits:

  • Bimodal Systems: In both scalar and vector bimodal examples, the FPF successfully captured two-peaked probability densities. In these scenarios, the standard Ensemble Kalman Filter (EnKF)—which effectively assumes a constant gain approximation—failed to represent the distribution accurately.
  • Benes Filter: This classic nonlinear filtering problem provides an analytical solution, allowing for a direct ground-truth comparison. The FPF demonstrated high accuracy in tracking the true posterior.
  • Comparison with SIR: The FPF consistently showed lower mean squared error (MSE) than SIR filters. By avoiding the discrete resampling steps of SIR, the FPF eliminates the "stochastic noise" that typically plagues importance sampling methods.

Discussion and Insights

Our analysis reveals a deep connection between the FPF and the Ensemble Kalman Filter. In the limit where the bandwidth $\epsilon \to \infty$, the diffusion map algorithm recovers the constant gain approximation, showing that the EnKF is a simplified, special case of the FPF framework. Furthermore, by proving the geometric ergodicity of the associated Markov chain, we ensure that the algorithm settles into a stable, unique solution rapidly.

From a computational standpoint, the $O(N^2)$ scaling of the diffusion map approach is significantly more efficient for high-dimensional state estimation than traditional Galerkin methods, which typically scale at $O(Nd^3)$.

Conclusion

This paper provides the first rigorous error analysis for diffusion map-based gain function approximation in the Feedback Particle Filter. While the current analysis relies on certain assumptions—such as log-concave distributions and compact support—the empirical results suggest the algorithm is robust even when these conditions are relaxed. Future work will focus on extending these error bounds to the gradient of the potential function (the actual gain used in the control law) and relaxing the current geometric assumptions to encompass a broader range of stochastic processes.

Summary updated

Abstract

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 $\Delta_\rho$. The numerical problem is to approximate this solution using {\em only} finitely many particles sampled from the probability distribution $\rho$. A diffusion map-based algorithm was proposed by the authors in a prior work 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^{\Delta_\rho}$. 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.
BibTeX
@misc{taghvaei2019gain,
  author = {Amirhossein Taghvaei and Prashant G. Mehta and Sean P. Meyn},
  title = {{Gain function approximation in the Feedback Particle Filter}},
  year = {2019},
  eprint = {1902.07263},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.07263},
}
Figure