# Non-asymptotic Identification of LTI Systems from a Single Trajectory

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

## Key facts

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

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

- [Provable Reinforcement Learning with a Short-Term Memory](https://mlsanity.com/paper/2202.03983/) (2022)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [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)
- [FedSysID: A Federated Approach to Sample-Efficient System Identification](https://mlsanity.com/paper/2211.14393/) (2022)
- [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)
- [Online Control of Unknown Time-Varying Dynamical Systems](https://mlsanity.com/paper/2202.07890/) (2022)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (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)
- [Physics-Regulated Deep Reinforcement Learning: Invariant Embeddings](https://mlsanity.com/paper/2305.16614/) (2023)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Provable Sim-to-real Transfer in Continuous Domain with Partial Observations](https://mlsanity.com/paper/2210.15598/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysis](https://mlsanity.com/paper/2311.18048/) (2023)
- [Model Stealing for Any Low-Rank Language Model](https://mlsanity.com/paper/2411.07536/) (2024)
- [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)
- [PAC-Bayesian theory for stochastic LTI systems](https://mlsanity.com/paper/2103.12866/) (2021)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through time](https://mlsanity.com/paper/2111.00070/) (2021)
- [Strong Consistency and Rate of Convergence of Switched Least Squares System Identification for Autonomous Markov Jump Linear Systems](https://mlsanity.com/paper/2112.10753/) (2021)
- [Learning the Uncertainty Sets for Control Dynamics via Set Membership: A Non-Asymptotic Analysis](https://mlsanity.com/paper/2309.14648/) (2023)

## Abstract (arXiv)

We consider the problem of learning a realization for a linear time-invariant (LTI) dynamical system from input/output data. Given a single input/output trajectory, we provide finite time analysis for learning the system's Markov parameters, from which a balanced realization is obtained using the classical Ho-Kalman algorithm. By proving a stability result for the Ho-Kalman algorithm and combining it with the sample complexity results for Markov parameters, we show how much data is needed to learn a balanced realization of the system up to a desired accuracy with high probability.