# Learning Linear Dynamical Systems via Spectral Filtering

arXiv: https://arxiv.org/abs/1711.00946 · HTML: https://mlsanity.com/paper/1711.00946/

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2017.

## Built on by (most cited first, 30 of 46)

- [Long-term Forecasting with TiDE: Time-series Dense Encoder](https://mlsanity.com/paper/2304.08424/) (2023)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Spectral State Space Models](https://mlsanity.com/paper/2312.06837/) (2023)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Flash STU: Fast Spectral Transform Units](https://mlsanity.com/paper/2409.10489/) (2024)
- [FutureFill: Fast Generation from Convolutional Sequence Models](https://mlsanity.com/paper/2410.03766/) (2024)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Universal Sequence Preconditioning](https://mlsanity.com/paper/2502.06545/) (2025)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Finite Sample Identification of Partially Observed Bilinear Dynamical Systems](https://mlsanity.com/paper/2501.07652/) (2025)
- [Universal Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2508.11990/) (2025)
- [Research Program: Theory of Learning in Dynamical Systems](https://mlsanity.com/paper/2512.19410/) (2025)
- [Time varying regression with hidden linear dynamics](https://mlsanity.com/paper/2112.14862/) (2021)
- [Fairness in Forecasting of Observations of Linear Dynamical Systems](https://mlsanity.com/paper/2209.05274/) (2022)
- [Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret](https://mlsanity.com/paper/2505.08982/) (2025)
- [Online Control in Population Dynamics](https://mlsanity.com/paper/2406.01799/) (2024)
- [Combining Federated Learning and Control: A Survey](https://mlsanity.com/paper/2407.11069/) (2024)
- [Long-Context Linear System Identification](https://mlsanity.com/paper/2410.05690/) (2024)
- [Provable Length Generalization in Sequence Prediction via Spectral Filtering](https://mlsanity.com/paper/2411.01035/) (2024)
- [UnHiPPO: Uncertainty-aware Initialization for State Space Models](https://mlsanity.com/paper/2506.05065/) (2025)
- [Continuous Latent Contexts Enable Efficient Online Learning in Transformers](https://mlsanity.com/paper/2605.09867/) (2026)
- [A New Approach to Controlling Linear Dynamical Systems](https://mlsanity.com/paper/2504.03952/) (2025)
- [Spectral Filtering for Complex Linear Dynamical Systems](https://mlsanity.com/paper/2601.22400/) (2026)
- [Elastic Spectral State Space Models for Train-Once Budgeted Inference](https://mlsanity.com/paper/2601.22488/) (2026)
- [Scalable Balanced Training of Conditional Generative Adversarial Neural Networks on Image Data](https://mlsanity.com/paper/2102.10485/) (2021)

## Abstract (arXiv)

We present an efficient and practical algorithm for the online prediction of discrete-time linear dynamical systems with a symmetric transition matrix. We circumvent the non-convex optimization problem using improper learning: carefully overparameterize the class of LDSs by a polylogarithmic factor, in exchange for convexity of the loss functions. From this arises a polynomial-time algorithm with a near-optimal regret guarantee, with an analogous sample complexity bound for agnostic learning. Our algorithm is based on a novel filtering technique, which may be of independent interest: we convolve the time series with the eigenvectors of a certain Hankel matrix.