# Improved rates for prediction and identification of partially observed linear dynamical systems

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2020.

## Built on by (most cited first, 12 of 12)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret](https://mlsanity.com/paper/2505.08982/) (2025)
- [Learning Low-dimensional Latent Dynamics from High-dimensional Observations: Non-asymptotics and Lower Bounds](https://mlsanity.com/paper/2405.06089/) (2024)
- [Nonconvex Linear System Identification with Minimal State Representation](https://mlsanity.com/paper/2504.18791/) (2025)
- [Spectral Filtering for Complex Linear Dynamical Systems](https://mlsanity.com/paper/2601.22400/) (2026)
- [The Complexity of Sequential Prediction in Dynamical Systems](https://mlsanity.com/paper/2402.06614/) (2024)
- [The Power of Second Order Methods for Sequence Preconditioning](https://mlsanity.com/paper/2605.08390/) (2026)
- [Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums](https://mlsanity.com/paper/2206.00861/) (2022)
- [Frequency Response Identification of Low-Order Systems: Finite-Sample Analysis](https://mlsanity.com/paper/2508.17142/) (2025)
- [Block Optimism for Nonstationary Bandits with Latent Linear Dynamics](https://mlsanity.com/paper/2610.00911/) (2026)

## Abstract (arXiv)

Identification of a linear time-invariant dynamical system from partial observations is a fundamental problem in control theory. Particularly challenging are systems exhibiting long-term memory. A natural question is how learn such systems with non-asymptotic statistical rates depending on the inherent dimensionality (order) d of the system, rather than on the possibly much larger memory length. We propose an algorithm that given a single trajectory of length T with gaussian observation noise, learns the system with a near-optimal rate of widetilde Oleft(√fracdTright) in H2 error, with only logarithmic, rather than polynomial dependence on memory length. We also give bounds under process noise and improved bounds for learning a realization of the system. Our algorithm is based on multi-scale low-rank approximation: SVD applied to Hankel matrices of geometrically increasing sizes. Our analysis relies on careful application of concentration bounds on the Fourier domain -- we give sharper concentration bounds for sample covariance of correlated inputs and for mathcal H_∞ norm estimation, which may be of independent interest.