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 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.

Average error of AR(s) models as a function of the number of auto-regressive terms $s$.

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.

  1. 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.
  2. Online Gradient Descent (OGD): The algorithm uses OGD to update the regression coefficients ($\theta$) in real-time.
  3. 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.

Heatmap of error ratios between Kalman and AR(2) models across varying noise levels.

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

Abstract

The 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