On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in
  Kalman Filters
  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.
