A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems

Motivated by the challenge of stabilizing unknown linear dynamical systems (LDS) from observations, we study the fundamental prerequisite of online prediction. Our goal is to achieve sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics rather than the full hidden-state dimension. We focus on the practically central regime of systems with low *instability complexity*—eigenvalues outside the real stable interval that do not decay rapidly, together with non-semisimple modes—potentially embedded in an otherwise stable real spectrum of much higher dimension; we write $k$ for this count. This regime is the primary setting in which stabilization is plausible: we show that many systems with high instability complexity cannot be stabilized without exponentially large controls. Thus, prediction is meaningful for stabilization precisely when the instability complexity is small. Within this regime, we introduce a unified online algorithm that handles every LDS (including systems with complex or exploding modes) with a learnable parameter count of $\widetilde{O}(k^2)$, completely independent of the number of stable real modes. Finally, we show that any bounded-coefficient filter-based predictor requires at least $k$ filter directions.