Abstract
The Kalman filter is a fundamental tool for time-series forecasting. This paper demonstrates that the influence of past observations on a Kalman filter's prediction decays exponentially, provided that the process noise is non-degenerate. This property allows for the approximation of Kalman filters using regression on a small window of recent observations. We show that process noise is essential for this decay; without it, forecasts may depend uniformly on the entire history. Leveraging this, we present a practical on-line algorithm for learning Linear Dynamical Systems (LDS) with the first regret bounds relative to the best Kalman filter in hindsight.
Introduction: The Challenge of Learning LDS
Linear Dynamical Systems (LDS) and Kalman filters are ubiquitous in time-series analysis, from aerospace to finance. However, learning the parameters of an LDS (such as the transition and observation matrices) is traditionally a non-convex optimization problem. Standard techniques like Expectation-Maximization (EM) are computationally intensive and prone to local optima.
To circumvent these issues, researchers have explored "improper learning"—approximating the LDS with a simpler, convex model class like auto-regression (AR). While AR models are easier to optimize, a critical theoretical question remained: Under what conditions is a finite-window AR model a sufficient substitute for a Kalman filter?
The Theory of Exponential Forgetting
The core contribution of this work is the proof that Kalman filters "forget" the distant past exponentially fast. For an observable LDS, the weights assigned to past observations in the filter's recurrence relation decay at an exponential rate.
The Essential Role of Noise
A surprising finding is that non-degenerate process noise ($W > 0$) is a prerequisite for this forgetting property. In systems with zero process noise, the filter may maintain a uniform memory of all past data, making it impossible to approximate with a short history window. Process noise acts as a stabilizer, forcing the model to prioritize recent information and enabling efficient learning through local windows.
A Practical On-Line Algorithm
Based on the exponential decay result, the authors propose an algorithm that predicts the next state as a linear combination of the last $s$ observations.
- Convexification: By treating the problem as auto-regression on a sliding window, the loss function becomes quadratic and the model linear, rendering the optimization entirely convex.
- Online Gradient Descent (OGD): The algorithm uses OGD to update the regression coefficients ($\theta$) in real-time.
- Efficiency: The per-update runtime is $O(s)$, where $s$ is the regression depth, making it significantly faster than traditional LDS estimation methods.
Key Results and Regret Bounds
This research provides the first regret bounds for learning an LDS relative to the class of Kalman filters. The algorithm achieves a regret of $O(\sqrt{T} + \epsilon T)$, meaning the average error of the AR model converges to that of the best possible Kalman filter as the window size $s$ increases and more data $T$ is processed.
Empirical tests on synthetic benchmarks validate these findings. As shown in the figures, the error of the AR approximation drops exponentially as the window size $s$ increases. Furthermore, the performance of the AR model remains robust across various levels of process and observation noise, provided the process noise is non-zero.
Conclusion
By proving the exponential forgetting property of Kalman filters, this work bridges the gap between classical control theory and modern convex optimization. It justifies the use of simple auto-regressive models for complex time-series tasks and provides a computationally efficient, theoretically grounded framework for on-line learning of Linear Dynamical Systems.
Summary updated