Abstract
The Kalman filter is a cornerstone of time-series forecasting and analysis. This paper demonstrates that the dependence of a Kalman filter's prediction on past observations decays exponentially, provided the process noise is non-degenerate. This property suggests that the Kalman filter can be effectively approximated by regression on a small window of recent observations. Conversely, we show that process noise is essential for this decay; without it, forecasts may depend uniformly on the entire history, complicating the learning process. Leveraging these insights, we present a practical on-line algorithm for improper learning of Linear Dynamical Systems (LDS) that achieves the first regret bounds relative to the class of Kalman filters. The algorithm is computationally efficient, with a per-update run-time linear in the regression depth.
Introduction
Linear Dynamical Systems (LDS) and their associated Kalman filters are fundamental tools in signal processing, control theory, and econometrics. Despite their ubiquity, learning the parameters of an LDS from data remains a significant challenge. Traditional approaches, such as Expectation-Maximization (EM) or maximum likelihood estimation, are often computationally expensive and prone to local minima due to the non-convex nature of the optimization landscape.
Recent research has shifted toward "improper learning," where the goal is not to recover the exact parameters of the underlying LDS, but rather to find a simpler predictive model—such as a linear function of past observations—that performs as well as the optimal Kalman filter. This paper bridges the gap between complex LDS theory and simple online learning by proving that Kalman filters naturally "forget" the distant past, justifying the use of local regression models.
The Theory of Exponential Forgetting
The core theoretical contribution of this work is the proof that the influence of an observation from $s$ steps ago on the current Kalman filter prediction decays exponentially at a rate of $\gamma^s$ (where $\gamma < 1$).
Crucially, the authors identify process noise—the inherent randomness in a system's state transition—as the necessary engine for this forgetting. In many engineering contexts, noise is viewed as a nuisance to be filtered out. However, in the context of online learning, process noise ensures that the system's state is constantly "refreshed," preventing the filter from being permanently influenced by the initial state or distant outliers. Without this noise, a Kalman filter might maintain a uniform dependence on all past data, making it impossible to approximate with a finite window of observations.
Mathematically, the proof relies on showing that the Kalman update behaves as a contraction mapping in a specific norm. This contractivity ensures that the error introduced by ignoring the distant past shrinks toward zero over time.
Algorithm: Online Gradient Descent for LDS
Building on the insight that only the recent past matters, the authors propose a simple and efficient Online Gradient Descent (OGD) algorithm. Instead of maintaining a complex state-space model, the algorithm treats forecasting as a rolling regression problem:
- Windowing: The algorithm maintains a vector of weights, $\theta$, corresponding to the last $s$ observations.
- Prediction: At each time step, it predicts the next value in the series as a linear combination of these $s$ observations.
- Update: Upon observing the true value, the algorithm updates $\theta$ using the gradient of the quadratic loss function.
Computational Efficiency: While some modern "spectral" learning methods scale cubically with time ($O(t^3)$), this OGD approach requires only $O(s)$ time per update. Since $s$ (the regression depth) is typically small due to exponential forgetting, the algorithm is well-suited for real-time applications.
Empirical Evaluation and Results
The paper validates its theoretical findings through both synthetic and real-world experiments.
Synthetic LDS
Using a 2D system adapted from existing literature, the authors verified that the prediction error of their windowed approach matches the decay predicted by their theory. This experiment confirmed that as process noise increases, the required window size $s$ for a given accuracy level decreases.
Real-World Financial Data
The algorithm was tested on the Dow Jones Industrial Average (DJIA) daily index from 1885 to 1962. The researchers evaluated the raw index as well as its first and second-order differences. The results were compared against "spectral filtering" methods, which are common benchmarks in the field. The simple OGD approach (specifically an AR(2) model) significantly outperformed spectral methods, which in some instances produced errors several orders of magnitude larger than the proposed algorithm.
Key Insights and Regret Bounds
This work provides the first regret bounds for learning against the class of Kalman filters. In the framework of online learning, regret measures the difference between the cumulative loss of the algorithm and the loss of the best possible Kalman filter chosen in hindsight. The authors prove a regret bound of $O(\sqrt{T} + \epsilon T)$, demonstrating that the average performance of their simple linear model converges toward the performance of the optimal LDS.
Conclusion
By proving that Kalman filters are inherently "forgetful" in the presence of process noise, this paper provides a rigorous theoretical foundation for using simple linear regression in time-series forecasting. The resulting algorithm is not only theoretically sound but also practically superior to more complex spectral methods in terms of both speed and accuracy. Future work may extend these results to non-quadratic loss functions and broader classes of dynamical systems.
Summary updated