Abstract
Linear State Space Models (SSMs) are fundamental in signal processing, but they often struggle with non-Gaussian inputs or hard physical constraints. Traditional approximation methods frequently suffer from "zero-variance stucking," where local variance estimates prematurely collapse to zero, leading to suboptimal solutions. This paper introduces Backward Filtering Forward Deciding (IBFFD), a novel iterative algorithm that reimagines the estimation process. By decoupling input decisions from variance updates, IBFFD avoids numerical traps, converges faster than standard alternatives like ADMM, and provides a robust framework for handling constraints in linear systems.
Introduction
Linear SSMs are ubiquitous in fields ranging from navigation to econometrics. While the Kalman Filter/Smoother provides an optimal solution for Gaussian noise, real-world applications often involve "spiky" (Laplace) priors or hard boundaries (e.g., physical limits on a robot's motion).
Existing approaches often utilize Normal with Unknown Parameters (NUP) to approximate non-Gaussian priors as Gaussians with shifting parameters. However, these methods are plagued by "zero-variance stucking": if an input's variance estimate hits zero during an iteration, it remains trapped there, regardless of the true solution. This leads to poor estimation accuracy and slow convergence.
The IBFFD Algorithm
The authors propose the IBFFD algorithm to overcome these limitations through a three-stage process:
- Backward Filtering (BF): A standard information filter pass gathers all "future" information about the state.
- Forward Deciding (FD): This novel step replaces the standard forward Kalman pass. The algorithm moves forward through time, making a discrete "decision" for each input $u_n$ sequentially.
- Proximal-like Updates: The decision rule utilizes closed-form expressions that act as proximal operators. Crucially, these rules ignore the current local variance estimate when updating the input, preventing the variance from collapsing and trapping the algorithm in a local minimum.
By dynamically adjusting a penalty parameter ($\beta$) during the forward pass, IBFFD can strictly enforce hard constraints (e.g., $u_n \ge a$) in every iteration without the need for extensive manual tuning.
Experimental Evaluation
Trend Filtering Benchmarks
The algorithm was tested on standard signal denoising tasks, such as the "Doppler" signal, using $L_1$ penalties to induce sparsity in differences.
As shown in the Doppler experiments, IBFFD consistently converged faster than the popular Alternating Direction Method of Multipliers (ADMM) and matched or exceeded the performance of the Primal-Dual Interior Point (PDIP) method. Notably, for higher-order trend filtering ($k=2$), IBFFD remained numerically stable where PDIP often struggled.
Real-World Climate Data
IBFFD was applied to annual global temperature anomalies (1880–2022) for shape-constrained regression, forcing the trend to be monotonic or convex.
In these tests, IBFFD consistently found lower-cost solutions than the previous Iterative Reweighted Least-squares Gaussian Estimation (IRLGE) method. The cost ratios $J(y_{IRLGE}) / J(y_{IBFFD})$ frequently exceeded 1, demonstrating that IBFFD successfully escaped the local minima that trapped IRLGE due to variance collapse.
Conclusion
IBFFD represents a significant advancement in non-Gaussian state-space estimation. By framing the problem as a blend of dynamic programming and NUP frameworks, the authors have created an algorithm that is both computationally efficient—scaling linearly with time steps ($N$)—and robust against the numerical instabilities of prior methods. While primarily designed for convex cost functions, future work may extend this "deciding" framework to non-linear models and more complex, non-separable priors.
Summary updated