On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filters

Mark Kozdoba, Jakub Marecek, Tigran T. Tchrakian, Shie Mannor

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:

  1. Windowing: The algorithm maintains a vector of weights, $\theta$, corresponding to the last $s$ observations.
  2. Prediction: At each time step, it predicts the next value in the series as a linear combination of these $s$ observations.
  3. 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

Abstract

Kalman filter is a key tool for time-series forecasting and analysis. We show that the dependence of a prediction of Kalman filter on the past is decaying exponentially, whenever the process noise is non-degenerate. Therefore, Kalman filter may be approximated by regression on a few recent observations. Surprisingly, we also show that having some process noise is essential for the exponential decay. With no process noise, it may happen that the forecast depends on all of the past uniformly, which makes forecasting more difficult. Based on this insight, we devise an on-line algorithm for improper learning of a linear dynamical system (LDS), which considers only a few most recent observations. We use our decay results to provide the first regret bounds w.r.t. to Kalman filters within learning an LDS. That is, we compare the results of our algorithm to the best, in hindsight, Kalman filter for a given signal. Also, the algorithm is practical: its per-update run-time is linear in the regression depth.
BibTeX
@inproceedings{kozdoba2019line,
  author = {Mark Kozdoba and Jakub Marecek and Tigran T. Tchrakian and Shie Mannor},
  title = {{On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filters}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=UoCkr1EveYu},
}

Loading related content...

Figure