PaperlayerView exact revision on arXiv

Source-linked AI summary

Feedback Particle Filter

Tao Yang, Prashant G. Mehta, Sean P. Meyn

arXiv:1302.6563v1math.NA

TL;DR

The paper addresses how to construct particle filters for nonlinear filtering while retaining a feedback structure and matching the true posterior. It formulates particle control through Kullback–Leibler optimization and an Euler–Lagrange equation. Under identical priors, the continuous-observation formulation achieves exact posterior matching, while numerical results support reduced variance and applications beyond conventional particle filtering.

  • Problem

    The paper seeks an alternative to conventional particle filtering that retains innovation-based feedback and avoids sampling-related issues.

  • Method

    The feedback particle filter chooses particle controls by minimizing Kullback–Leibler divergence, with the optimal control characterized by an Euler–Lagrange equation and innovation-error feedback.

  • Results

    With identical initial priors, the continuous-observation feedback particle filter matches the true posterior exactly under the stated conditions.

  • Takeaways & Limitations

    The feedback particle filter generalizes the Kalman filter’s innovation and feedback structure to nonlinear non-Gaussian problems without requiring resampling.

  • Takeaways & Limitations

    The derivation of the Euler–Lagrange equation is heuristic, and rigorous justification is left for future work.

Abstract

from arXiv · show

A new formulation of the particle filter for nonlinear filtering is presented, based on concepts from optimal control, and from the mean-field game theory. The optimal control is chosen so that the posterior distribution of a particle matches as closely as possible the posterior distribution of the true state given the observations. This is achieved by introducing a cost function, defined by the Kullback-Leibler (K-L) divergence between the actual posterior, and the posterior of any particle. The optimal control input is characterized by a certain Euler-Lagrange (E-L) equation, and is shown to admit an innovation error-based feedback structure. For diffusions with continuous observations, the value of the optimal control solution is ideal. The two posteriors match exactly, provided they are initialized with identical priors. The feedback particle filter is defined by a family of stochastic systems, each evolving under this optimal control law. A numerical algorithm is introduced and implemented in two general examples, and a neuroscience application involving coupled oscillators. Some preliminary numerical comparisons between the feed- back particle filter and the bootstrap particle filter are described.

I. INTRODUCTION

The paper introduces a feedback particle filter whose controlled particles approximate the nonlinear filtering posterior through a Kullback–Leibler variational formulation. Its optimal control has an innovation-error feedback structure, achieves exact posterior matching under stated continuous-observation conditions, and avoids particle resampling.

  • Method: The feedback particle filter defines each particle through a controlled stochastic system designed to approximate the true posterior distribution.The control is synthesized as an optimal-control problem using Kullback–Leibler divergence between particle and true posteriors.
  • Method: The optimal control is characterized by an Euler–Lagrange boundary-value problem and an innovation-error feedback term.The gain function is obtained from the boundary-value problem and is evaluated over time.
  • Consistency: Under optimal control and identical initial priors, the particle posterior matches the true posterior exactly for continuous-observation diffusions.The paper states this consistency result for all times under the specified conditions.
  • Advantages: Unlike conventional importance-sampling particle filters, the feedback particle filter does not require resampling.The authors associate this with greater implementation flexibility and fewer sampling-related issues.
  • Structure: The innovation error compares each particle’s predicted observation with the population prediction, preserving a Kalman-like feedback structure in nonlinear systems.For linear systems the gain is the Kalman gain; for nonlinear systems it becomes a state-dependent function.
  • Applications: Numerical results support reduced variance relative to the bootstrap filter, and a coupled-oscillator example illustrates a possible neuroscience application.The paper presents preliminary comparisons and describes the application as potentially more neuro-biologically plausible than importance-sampling approaches.

A. Comparison with Relevant Literature

The paper formulates particle filtering as a partially observed control problem and distinguishes its variational feedback construction from related controlled-filter approaches. Its formulation derives innovation feedback without smoothing the observation innovation and requires a gain-function boundary-value problem.

  • Problem formulation: The control objective is to choose particle controls so that the particle distribution approximates the nonlinear filtering distribution.The paper casts this as a partially observed optimal-control problem with the joint particle and state process used in the formulation.
  • Comparison with related work: The variational formulation differs from related approaches based on finite-horizon Hamilton–Jacobi–Bellman equations or smooth approximations of the innovation process.The feedback particle filter derives its innovation-error formula directly from the variational analysis.
  • Comparison with related work: The feedback particle filter and the compared filter both require solving a boundary-value problem to obtain the gain function.The paper states that the resulting computational complexity is the same, while noting limitations of a particular alternative BVP solution.
  • Formulation: The continuous-time formulation is obtained as a limiting case of the continuous-discrete filtering problem.The paper introduces the feedback particle filter after describing the variational setup for sampled observations.
  • Applications: The paper develops numerical algorithms and examples, including a neuroscience application involving coupled oscillator models.The cited application is presented as one motivation for the work.

A. Belief Maps

The belief-map formulation separates diffusion propagation from observation updating and chooses admissible particle controls to make the particle update approximate the true Bayesian update. The control is selected by minimizing Kullback–Leibler divergence, yielding an Euler–Lagrange boundary-value problem.

  • Belief Maps: The true and particle conditional densities are propagated through recursions that represent their respective filtering mappings.The observation history conditions the densities, while the particle mapping depends on the selected control input.
  • Belief Maps: Both mappings share a diffusion-propagation step defined by the Kolmogorov forward equation before their observation-update steps diverge.The second mapping component for the true density follows Bayes’ rule, whereas the particle mapping depends on the admissible control.
  • Admissibility: Admissible controls are represented by sufficiently smooth maps whose transformation remains nondegenerate through the condition 1+v′(x) ≠ 0.The definition requires twice continuous differentiability and a non-zero Jacobian factor.
  • Variational Problem: The control objective is to choose an admissible input so that the particle mapping approximates the true mapping.The paper compares the resulting densities using the Kullback–Leibler divergence metric.
  • Variational Problem: The minimizing control function satisfies an Euler–Lagrange boundary-value problem.The paper identifies the minimizer of the KL-based optimization problem with the solution of the corresponding E–L BVP.

III. FEEDBACK PARTICLE FILTER

The feedback particle filter chooses control functions through an Euler–Lagrange boundary value problem so the particle posterior evolves identically to the true posterior under matching priors. In the ideal setting, this yields consistency for all times, while practical implementations replace the posterior with an empirical particle distribution.

  • Filter construction: The particle model uses controlled Itô diffusions whose conditional distribution p(x,t) is designed to match the true posterior p∗(x,t).The control functions are chosen so the two conditional-distribution evolution equations coincide.
  • Filter construction: The control pair {u,K} is constructed from an Euler–Lagrange boundary value problem, with K determined by the BVP and u obtained from the resulting posterior quantities.The control is assumed admissible under the stated regularity and density conditions.
  • Gain properties: Existence and uniqueness of the gain-function solution hold under Assumption A1, and K(x,t) is nonnegative when h′(x) ≥ 0.The positivity conclusion is conditional on the monotonicity of h.
  • Consistency: Under matching initial distributions and the prescribed control functions, the particle and true posterior evolution equations are identical for all t ≥ 0.This is the paper’s ideal consistency result.
  • Consistency: The ideal theorem assumes the gain is computed from the posterior itself, whereas practical algorithms replace that posterior with the empirical distribution of N particles.The empirical distribution approximates the posterior as N increases, with weak convergence in general and almost sure convergence under additional sample-path conditions.
  • Scope: The paper extends the methodology beyond Gaussian process noise by replacing the process-noise model, while other observation-noise models require modifying the conditional distribution in the optimization problem.The derivation then proceeds through first-variation analysis.

C. Example: Linear Model

In the linear Gaussian case, the feedback particle filter recovers the Kalman filtering posterior, with a gain obtained from the boundary value problem. The multivariable extension requires solving a BVP at every time step and exposes limitations of an alternative gradient-form gain.

  • Scalar linear Gaussian case: In the linear Gaussian model, the gain-function BVP has an explicit solution when the particle posterior is Gaussian.The formula is verified by direct substitution into the BVP.
  • Scalar linear Gaussian case: The optimally controlled particle filter has posterior distributions that coincide with the true conditional distributions characterized by continuous-time Kalman equations.Both posteriors are Gaussian, with conditional means and covariances given by the corresponding SDE and ODE.
  • Scalar linear Gaussian case: The resulting linear particle system is impractical if it requires the conditional mean and variance directly; in practice, these quantities are estimated from sample means and covariances.The mean-field form represents the limit as N → ∞.
  • Multivariable extension: For multivariable systems, the gain is vector-valued and is obtained by solving a multivariable boundary value problem at each time step.The formulation uses divergence, the Laplacian, and a Wong–Zakai correction in the multivariable dynamics.
  • Multivariable extension: A Green’s-function representation can produce an explicit gain formula, but the resulting control law may fail to be admissible.This issue is identified as also arising in prior work by Crisan and Xiong.

E. Comparison with Crisan and Xiong’s Filter

Compared with Crisan and Xiong’s filter, the feedback particle filter avoids smooth innovation approximations and retains consistency, although both methods require comparable boundary-value-problem computations. The alternative gradient-form gain can fail even in linear Gaussian settings.

  • Consistency comparison: Without a smooth approximation, the compared filter lacks consistency because an extra second-order term is absent from the Kushner–Stratonovich equation.The mismatch arises when the alternative formulation is expressed in Stratonovich form.
  • Consistency comparison: The feedback particle filter does not require a smooth approximation and achieves consistency through a modified innovation-error definition derived from the variational formulation.The innovation error is obtained by analyzing the variational problem rather than assumed beforehand.
  • Computational comparison: Both filters have equal computational overhead because each requires approximating the same integral and dividing by a suitably regularized density estimate.The Poisson-equation formulation is described as convenient for numerical approximation.
  • Gain comparison: The gradient-form gain is not the correct multivariable gain even for linear models, because the Kalman gain solves the BVP but is not of that form.Consequently, the associated integral solution does not equal the Kalman gain for d ≥ 2.
  • Gain comparison: The gradient-form gain is unbounded, with both E[|K_g|] and E[|K_g|^2] infinite, causing numerical issues from large unbounded gains.The paper contrasts this with the feedback particle filter using the Kalman gain, which works in theory and practice.
  • Scope and limitations: The multivariable BVP solution is not unique in general, although uniqueness holds when the gain is restricted to gradient form.The paper notes that a fuller comparison with the alternative filter requires further investigation.

A. Direct Numerical Approximation of the BVP solution

The paper develops direct numerical approximations for the feedback particle filter’s gain function by approximating the density and related integrals, with computational alternatives for implementation.

  • Direct approximation: The closed-form BVP solution provides a direct route to numerically approximating the gain function.An efficient O(N^2) algorithm can be constructed from the resulting expression.
  • Approximation steps: The approximation uses a sample mean, integrand approximation, and density approximation, such as a Gaussian sum.The density approximation includes a regularization parameter ϵ that can decrease as N grows.
  • Gain evaluation: The resulting gain function is evaluated only at particle locations, reducing the required evaluation domain.The gain construction uses the Heaviside function in its numerical form.
  • Implementation: The implementation uses the Stratonovich filter with Euler discretization, while alternative gain approximations include sum-of-Gaussian and Fourier-series methods.A DNS-based algorithm is also summarized for gain synthesis.
  • Method comparison: The feedback particle filter replaces the nonlinear filtering PDE with a linear BVP for obtaining the gain function at each time.The approach has parallels with vortex element methods, which also evolve many particles using a vector field obtained from a linear BVP.
  • Computational considerations: The BVP must be solved at every time step and requires density approximation, making this the main computational cost and motivating further analysis of efficiency.The paper identifies robustness and self-correction as expected benefits but states that a complete comparison requires further analysis.

V. NUMERICS

Numerical experiments evaluate the feedback particle filter in linear, nonlinear, and oscillator settings. The results show accurate tracking and favorable behavior in several comparisons, while gain approximation can increase computational cost.

  • Linear Gaussian case: With N = 10,000 particles, the linear experiment compares the state path and particle conditional mean, while estimated variance is compared with the true Kalman-filter variance.The results also examine sensitivity to particle count, including N = 100.
  • Linear Gaussian case: The feedback and bootstrap filters are compared using mean-squared error and computational time over particle counts from 20 to 1000.The relative error is defined using the Kalman filter as the optimal linear solution.
  • Linear Gaussian case: For unstable signal dynamics with α > 0, bootstrap-filter simulations blew up, whereas the feedback particle filter is described as provably stable under model observability.The comparison is illustrated for α = 0.5 in the MSE plot.
  • Linear Gaussian case: In the linear Gaussian implementation, the feedback particle filter has lower computational cost because it avoids resampling.When the gain is approximated with Algorithm 2, MSE remains comparable but computation time exceeds that of the bootstrap filter.
  • Nonlinear example: In the nonlinear example, two initial Gaussian clusters merge into one cluster that tracks the true state, including transition events.The state transitions between two stable equilibria when process noise is present, and the reported tracking error remains small during transitions.
  • Nonlinear oscillator: For the nonlinear oscillator, the estimated mean is compared with the true state, while first and second density harmonics and an empirical distribution are examined.The density is reported to be approximately harmonic during the displayed time window.

VI. CONCLUSIONS

The paper introduces the feedback particle filter as a nonlinear, non-Gaussian generalization of Kalman filtering that retains innovation-error and feedback structures. Numerical results support feedback as a way to reduce high variance in conventional particle filtering.

  • Conclusions: The feedback particle filter generalizes the Kalman filter to a broad class of nonlinear non-Gaussian problems.The formulation retains innovation-error and feedback structures associated with the Kalman filter.
  • Conclusions: Numerical results support feedback as a mechanism that can reduce high variance sometimes observed in conventional particle filters.The conclusion points to the comparison in Fig. 3 as evidence for this claim.
  • Conclusions: The authors expect the feedback particle filter to provide an integrated framework for nonlinear non-Gaussian filtering problems.This expectation is presented as an extension of the structural role of Kalman filtering in larger systems.

VII. APPENDIX

The appendix develops the variational and stochastic-analysis foundations of the feedback particle filter. It transforms the K-L optimization into an Euler-Lagrange problem and establishes the conditional particle evolution through Itô calculus and filtering identities.

  • Variational formulation: The control-design problem is formulated by expressing the K-L divergence after a coordinate transformation and minimizing the resulting variational objective.The minimizer is characterized through the first variation and an Euler-Lagrange equation.
  • Filtrations: The appendix defines the observation and particle filtrations and treats them as independent by construction.The observation trajectory is represented by Z_t and its history.
  • Well-posedness: Under Lipschitz assumptions on the controlled drift and gain, the particle evolution has a unique solution adapted to the enlarged filtration.The enlarged filtration combines particle noise and observation history.
  • Conditional density: The conditional density p(x,t) is defined through expectations of bounded measurable test functions conditioned on the observation history.This density is the conditional distribution of a particle given the observations.
  • Proof structure: The proof architecture relies on a key lemma for adapted processes, followed by conditional-expectation and integration-by-parts arguments.The appendix states the lemma and then applies it in proving the main proposition.
  • Stochastic analysis: Itô’s formula followed by conditional expectation yields the evolution equations used to analyze the controlled particle system.The forward equation is obtained using integration by parts.

D. Euler-Lagrange equation for the continuous-time filter

The continuous-time Euler–Lagrange equation is obtained by taking a formal limit of the discrete-time boundary-value problem. Its solution establishes that the controlled particle density and nonlinear-filter density satisfy identical stochastic differential equations.

  • Continuous-time limit: The continuous-time control and observation models are obtained as the limit of their discrete-time counterparts.The derivation substitutes the continuous-time models into the discrete-time E-L boundary-value problem.
  • Continuous-time limit: Collecting terms of order O(ΔZ_t) and O(Δt) yields the continuous-time ordinary differential equations.The derivation simplifies the resulting terms after taking the small-time limit.
  • Euler-Lagrange equation: The E-L equation for the gain function K is equation (70), identified with equation (24).The proof derives the final E-L form from the preceding ODE relations and boundary conditions.
  • Limitations: The derivation of the Euler–Lagrange equation is heuristic because the justification of Step 1 remains unresolved.The authors identify rigorous justification or an alternative argument as future work, and note additional regularity requirements for later calculations.
  • Consistency: When K solves the E-L boundary-value problem, the controlled density p and filtering density p* are defined by identical stochastic differential equations.The argument compares the forward equation for p with the Kushner–Stratonovich equation for p* and obtains the same SDE.

G. Proof of Thm. 3.5

The multivariable analysis compares the Kalman gain with another solution of the gain boundary-value problem. It shows that the Kalman gain solves the problem, while the alternative integral solution differs from it and is not integrable in the relevant setting.

  • Alternative gain solution: For d ≥ 2, the integral solution K_g is not equal to the Kalman gain and is unbounded as |x| → ∞.The proposition also states that K_g is not square-integrable with respect to p.
  • Comparison of solutions: The multivariable result distinguishes the boundary-value problem's Kalman-gain solution from the integral representation K_g.The proof establishes the distinction through the failure of the gradient form and the asymptotic behavior of K_g.
  • Kalman gain: For the multivariable linear Gaussian system, the Kalman gain is a solution of the boundary-value problem.The proposition verifies this solution by direct substitution when the density is Gaussian.
  • Kalman gain: For a nonzero Kalman gain, no function φ exists such that pK = ∇φ.This rules out the gradient representation for the Kalman-gain solution under the stated conditions.
Loading 1302.6563v1…