Closed-form Filtering for Non-linear Systems

Théophile Cantelobre, Carlo Ciliberto, Benjamin Guedj, Alessandro RudiarXiv 2024 · DOI · arXiv

Abstract

Sequential Bayesian filtering is a cornerstone of signal processing and robotics, yet practitioners often face a trade-off between the efficiency of Kalman filters and the flexibility of particle filters. This paper introduces a novel framework using Gaussian Positive Semi-Definite (PSD) Models to perform non-linear filtering in closed form. By representing transition and observation kernels as PSD models, the authors achieve a computational complexity of $O(\epsilon^{-3/2})$, surpassing the $O(\epsilon^{-2})$ limit of traditional particle filters while providing rigorous stability guarantees.

Introduction

In the domain of state estimation, the challenge lies in the "correction" and "prediction" steps of Bayesian filtering. These steps require multiplying probability distributions and performing marginalization through integration. For non-linear systems, these integrals typically lack analytical solutions, necessitating the use of Sequential Monte Carlo (Particle Filtering). However, particle filters suffer from high computational costs and a lack of functional structure. This research proposes a middle ground: a method as flexible as particle filters but as mathematically structured as the Kalman Filter.

Methodology: Gaussian PSD Models and PSDFilter

The proposed approach leverages Gaussian PSD Models, which can be viewed as an expressive extension of Gaussian Mixture Models (GMMs). Unlike standard GMMs, a Gaussian PSD Model is defined as a "sum-of-squares" of linear combinations of kernels. This ensures non-negativity—a prerequisite for probability densities—while allowing for greater expressivity through negative internal coefficients.

The authors introduce two primary algorithms. The first, LEARNRANKONE, is an offline procedure used to learn PSD approximations of system dynamics from data or function evaluations.

Algorithm 1: The LEARNRANKONE algorithm for offline learning of PSD approximations.

The second, PSDFilter, is the online filtering component. It recursively updates the state distribution using linear algebra operations (matrix-vector products), enabling exact closed-form Bayesian updates when transitions and observations are represented as Gaussian PSD Models.

Key Insights

  • Sum-of-Squares Advantage: The PSD framework bypasses the need for sampling by using kernel-based models that can approximate smooth densities to arbitrary precision.
  • Efficiency Gains: For smooth systems, the PSDFilter achieves a target error $\epsilon$ with a complexity of $O(\epsilon^{-3/2})$, theoretically outperforming particle filters in high-precision scenarios.
  • Filter Stability: The paper provides proofs for filter stability, demonstrating that the system converges to the true distribution even with an incorrect initial state estimate.
  • Adaptive Complexity: The regularity (smoothness) of the system dictates the number of "anchor points" required, allowing the algorithm to scale its complexity based on problem difficulty.

Theoretical Results

The authors derive exact formulas for the product, integral, and marginalization of PSD models. Theorem 6 establishes a rigorous bound on the Total Variation (TV) distance between the estimated and optimal filters, showing exponential error decay over time. For infinitely differentiable kernels, memory costs scale as $O(\epsilon^{-1})$ and computational costs as $O(\epsilon^{-1.5})$.

Limitations and Future Directions

While the complexity scales well with error, the constants involved still depend on the state dimension $d$, potentially limiting application in very high-dimensional spaces. Future work may involve more sophisticated "active learning" for anchor point selection and empirical validation in real-world robotics benchmarks like KITTI or MuJoCo.

Summary updated

Abstract

Sequential Bayesian Filtering aims to estimate the current state distribution of a Hidden Markov Model, given the past observations. The problem is well-known to be intractable for most application domains, except in notable cases such as the tabular setting or for linear dynamical systems with gaussian noise. In this work, we propose a new class of filters based on Gaussian PSD Models, which offer several advantages in terms of density approximation and computational efficiency. We show that filtering can be efficiently performed in closed form when transitions and observations are Gaussian PSD Models. When the transition and observations are approximated by Gaussian PSD Models, we show that our proposed estimator enjoys strong theoretical guarantees, with estimation error that depends on the quality of the approximation and is adaptive to the regularity of the transition probabilities. In particular, we identify regimes in which our proposed filter attains a TV $\epsilon$-error with memory and computational complexity of $O(\epsilon^{-1})$ and $O(\epsilon^{-3/2})$ respectively, including the offline learning step, in contrast to the $O(\epsilon^{-2})$ complexity of sampling methods such as particle filtering.
BibTeX
@misc{cantelobre2024closed,
  author = {Théophile Cantelobre and Carlo Ciliberto and Benjamin Guedj and Alessandro Rudi},
  title = {{Closed-form Filtering for Non-linear Systems}},
  year = {2024},
  eprint = {2402.09796},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.09796},
}
Figure