# Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples

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

## Key facts

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

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

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Distributed Online System Identification for LTI Systems Using Reverse Experience Replay](https://mlsanity.com/paper/2207.01062/) (2022)
- [Learning Low-dimensional Latent Dynamics from High-dimensional Observations: Non-asymptotics and Lower Bounds](https://mlsanity.com/paper/2405.06089/) (2024)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Regret Analysis of Distributed Online Control for LTI Systems with Adversarial Disturbances](https://mlsanity.com/paper/2310.03206/) (2023)
- [The Power of Second Order Methods for Sequence Preconditioning](https://mlsanity.com/paper/2605.08390/) (2026)
- [System Identification via Nuclear Norm Regularization](https://mlsanity.com/paper/2203.16673/) (2022)

## Abstract (arXiv)

In this work, we study the problem of learning partially observed linear dynamical systems from a single sample trajectory. A major practical challenge in the existing system identification methods is the undesirable dependency of their required sample size on the system dimension: roughly speaking, they presume and rely on sample sizes that scale linearly with respect to the system dimension. Evidently, in high-dimensional regime where the system dimension is large, it may be costly, if not impossible, to collect as many samples from the unknown system. In this paper, we will remedy this undesirable dependency on the system dimension by introducing an ℓ1-regularized estimation method that can accurately estimate the Markov parameters of the system, provided that the number of samples scale logarithmically with the system dimension. Our result significantly improves the sample complexity of learning partially observed linear dynamical systems: it shows that the Markov parameters of the system can be learned in the high-dimensional setting, where the number of samples is significantly smaller than the system dimension. Traditionally, the ℓ1-regularized estimators have been used to promote sparsity in the estimated parameters. By resorting to the notion of "weak sparsity", we show that, irrespective of the true sparsity of the system, a similar regularized estimator can be used to reduce the sample complexity of learning partially observed linear systems, provided that the true system is inherently stable.