# Near optimal finite time identification of arbitrary linear dynamical systems

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

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2018.

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

- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach](https://mlsanity.com/paper/2112.03432/) (2021)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems](https://mlsanity.com/paper/2105.11558/) (2021)
- [FedSysID: A Federated Approach to Sample-Efficient System Identification](https://mlsanity.com/paper/2211.14393/) (2022)
- [Joint Learning of Linear Time-Invariant Dynamical Systems](https://mlsanity.com/paper/2112.10955/) (2021)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Identifying the Dynamics of a System by Leveraging Data from Similar Systems](https://mlsanity.com/paper/2204.05446/) (2022)
- [Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds](https://mlsanity.com/paper/2111.07018/) (2021)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (2023)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [Learning Personalized Models with Clustered System Identification](https://mlsanity.com/paper/2304.01395/) (2023)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss](https://mlsanity.com/paper/2402.05928/) (2024)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Sparsity in Partially Controllable Linear Systems](https://mlsanity.com/paper/2110.06150/) (2021)
- [An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysis](https://mlsanity.com/paper/2311.18048/) (2023)
- [Learning the Dynamics of Autonomous Linear Systems From Multiple Trajectories](https://mlsanity.com/paper/2203.12794/) (2022)
- [Learning Dynamical Systems by Leveraging Data from Similar Systems](https://mlsanity.com/paper/2302.04344/) (2023)
- [On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure](https://mlsanity.com/paper/2110.07112/) (2021)

## Abstract (arXiv)

We derive finite time error bounds for estimating general linear time-invariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a self--normalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signal-to-noise ratio is high.