Variable Splitting Methods for Constrained State Estimation in Partially Observed Markov Processes

Rui Gao, Filip Tronarp, Simo Särkkä

TL;DR

This paper introduces a highly efficient framework for state estimation (like tracking a ship or robot) that respects physical constraints, such as "don't go through this wall" or "stay within this speed limit." By combining variable splitting optimization techniques (like ADMM) with the recursive efficiency of Kalman smoothing, the authors create a method that is significantly faster and more scalable than traditional batch optimization, especially for long time-series data.

What Problem Does This Paper Address?

In fields like robotics, indoor positioning, and target tracking, we use "state estimation" to figure out where an object is based on noisy sensor data. Often, we have prior knowledge or physical laws that act as constraints (e.g., a car cannot drive through a building, or a ship must stay within a specific channel).

The challenge is that incorporating these equality and inequality constraints into the math makes the problem much harder to solve. Traditional "batch" optimization methods treat the entire history of the object as one giant vector. While accurate, these methods become incredibly slow or run out of memory as the duration of the tracking increases (the "curse of dimensionality"). The authors aim to bridge the gap between high-accuracy constrained optimization and the high-speed recursive filters typically used in real-time signal processing.

Methods

The authors propose a general framework that merges two powerful mathematical worlds:

  1. Variable Splitting (ADMM, PRS, SBM): These are optimization algorithms that break a complex, constrained problem into smaller, easier-to-solve subproblems. They introduce "auxiliary variables" to decouple the cost function from the constraints.
  2. Markovian Structure (Kalman Smoothing): The authors realize that in a state-space model, the "state" at one moment only depends on the previous moment. They leverage this "Markov property" to solve the main subproblem.

The "Aha!" Moment: The authors show that the subproblem for updating the state sequence can be reformulated as a standard state-space model where the constraints are treated as "artificial measurements." This allows them to use the Kalman Smoother (KS) for linear systems or the Iterated Extended Kalman Smoother (IEKS) for nonlinear systems.

Because Kalman smoothers process data recursively, the computational cost grows linearly with time ($O(T)$), whereas batch methods often grow cubically or worse.

Datasets

The paper evaluates the methods using a simulated four-dimensional ship tracking model.

  • State: Includes 2D position and 2D velocity.
  • Measurements: Range-bearing data from two stationary sensors.
  • Constraint: A nonlinear inequality constraint representing a boundary the ship cannot cross ($1.25 - \sin(x_{2,t}) - x_{4,t} \le 0$).
  • Scale: They tested the algorithms on sequences ranging from $10^3$ to $10^6$ time steps to demonstrate scalability.

Key Insights and Ideas

  • Constraints as Data: By treating constraints as "pseudo-measurements" with specific noise profiles, the authors can plug them directly into existing, highly-optimized Kalman filtering architectures.
  • Scalability is King: The primary advantage isn't just accuracy—it's memory and speed. By avoiding large matrix inversions associated with batch processing, they can handle datasets that are orders of magnitude larger than what standard solvers can manage.
  • Algorithmic Flexibility: The framework isn't tied to just one optimizer. It can be instantiated using ADMM (Alternating Direction Method of Multipliers), PRS (Peaceman–Rachford splitting), or SBM (Split Bregman method), depending on the specific convergence needs of the application.

Key Results

  • Speedup: For a sequence of $10^4$ steps, the proposed CIEKS-SBM method took about 26.7 seconds, while the batch SBM method took 2,193 seconds—a nearly 80x speedup.
  • Memory Efficiency: At $10^5$ time steps, all traditional batch methods failed due to running out of memory ("Out of Memory"). The proposed methods handled $10^6$ steps (one million data points) in roughly 30 to 135 minutes on standard hardware.
  • Accuracy: The constrained estimates were significantly closer to the "ground truth" trajectory compared to unconstrained estimates, which often drifted into "forbidden" zones.

Limitations and Future Work

  • Local Convergence: For highly nonlinear systems, the paper provides a "local" convergence theorem. This means if the initial guess is very far from the truth, the algorithm might get stuck in a local minimum rather than finding the global best fit.
  • Parameter Tuning: Like many variable splitting methods, the performance depends on choosing the right penalty parameters ($\rho_1, \rho_2$). The paper doesn't provide an automated way to tune these for every scenario.
  • Future Directions: The authors suggest extending this framework to even more complex models, such as those involving "jump" Markov systems or systems with non-Gaussian noise.

Summary updated

Abstract

In this letter, we propose a class of efficient, accurate, and general methods for solving state-estimation problems with equality and inequality constraints. The methods are based on recent developments in variable splitting and partially observed Markov processes. We first present the generalized framework based on variable splitting, then develop efficient methods to solve the state-estimation subproblems arising in the framework. The solutions to these subproblems can be made efficient by leveraging the Markovian structure of the model as is classically done in so-called Bayesian filtering and smoothing methods. The numerical experiments demonstrate that our methods outperform conventional optimization methods in computation cost as well as the estimation performance.
BibTeX
@article{gao2020variable,
  author = {Rui Gao and Filip Tronarp and Simo Särkkä},
  title = {{Variable Splitting Methods for Constrained State Estimation in Partially Observed Markov Processes}},
  journal = {IEEE Signal Processing Letters},
  year = {2020},
  url = {https://openreview.net/forum?id=_LLdFsgYeU},
}

Loading related content...

Figure