mlsanityData to 7 Oct 2026

A New Approach to Learning Linear Dynamical Systems

arXiv 2301.09519 ↗First posted 23 Jan 2023math.OC cs.DS cs.LGcited by 23

Not on the map. Why?

Abstract (arXiv)

Linear dynamical systems are the foundational statistical model upon which control theory is built. Both the celebrated Kalman filter and the linear quadratic regulator require knowledge of the system dynamics to provide analytic guarantees. Naturally, learning the dynamics of a linear dynamical system from linear measurements has been intensively studied since Rudolph Kalman's pioneering work in the 1960's. Towards these ends, we provide the first polynomial time algorithm for learning a linear dynamical system from a polynomial length trajectory up to polynomial error in the system parameters under essentially minimal assumptions: observability, controllability, and marginal stability. Our algorithm is built on a method of moments estimator to directly estimate Markov parameters from which the dynamics can be extracted. Furthermore, we provide statistical lower bounds when our observability and controllability assumptions are violated.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 42 of its 73 references that are in the map. First posted on arXiv 23 Jan 2023.

Builds on

42 of 73 references.

References · 42

  1. 2018Learning Without Mixing: Towards A Sharp Analysis of Linear System Identificationcited by 158
  2. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  3. 2018Near optimal finite time identification of arbitrary linear dynamical systemscited by 89
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2016Gradient Descent Learns Linear Dynamical Systemscited by 78
  6. 2018Non-asymptotic Identification of LTI Systems from a Single Trajectorycited by 77
  7. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  8. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  9. 2019Finite Sample Analysis of Stochastic System Identificationcited by 67
  10. 2017Finite Time Identification in Unstable Linear Systemscited by 66
  11. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
  12. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 52
30 more
  1. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  2. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  3. 2017Sub-Gaussian estimators of the mean of a random vectorcited by 47
  4. 2017Learning Linear Dynamical Systems via Spectral Filteringcited by 46
  5. 2019List-Decodable Linear Regressioncited by 42
  6. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  7. 2020Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectoriescited by 38
  8. 2018Spectral Filtering for General Linear Dynamical Systemscited by 37
  9. 2019List Decodable Learning via Sum of Squarescited by 37
  10. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 31
  11. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  12. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
  13. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  14. 2019Learning Some Popular Gaussian Graphical Models without Condition Number Boundscited by 20
  15. 2020List Decodable Mean Estimation in Nearly Linear Timecited by 20
  16. 2020Outlier-Robust Clustering of Non-Spherical Mixturescited by 19
  17. 2020Robust estimation via generalized quasi-gradientscited by 19
  18. 2020No-Regret Prediction in Marginally Stable Systemscited by 18
  19. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  20. 2019Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyondcited by 14
  21. 2020List Decodable Subspace Recoverycited by 13
  22. 2019Nonparametric Finite Time LTI System Identificationcited by 11
  23. 2020SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memorycited by 11
  24. 2019Non-asymptotic Closed-Loop System Identification using Autoregressive Processes and Hankel Model Reductioncited by 9
  25. 2020Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samplescited by 9
  26. 2022List-Decodable Covariance Estimationcited by 8
  27. 2020List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Timecited by 7
  28. 2022Efficient learning of hidden state LTI state space models of unknown ordercited by 7
  29. 2021Kalman Filtering with Adversarial Corruptionscited by 6
  30. 2020Adaptive Control and Regret Minimization in Linear Quadratic Gaussian (LQG) Settingcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 8; 2025: 7; 2026: 5.

23 papers.

Sort:

  1. 2023Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systemscited by 10
  2. 2023An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysiscited by 9
  3. 2024Model Stealing for Any Low-Rank Language Modelcited by 9
  4. 2024Structure learning of Hamiltonians from real-time evolutioncited by 8
  5. 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
  6. 2024Learning Linear Dynamics from Bilinear Observationscited by 6
  7. 2025Universal Sequence Preconditioningcited by 6
  8. 2025Universal Learning of Nonlinear Dynamicscited by 5
  9. 2025Finite Sample Identification of Partially Observed Bilinear Dynamical Systemscited by 4
  10. 2024Learning Low-dimensional Latent Dynamics from High-dimensional Observations: Non-asymptotics and Lower Boundscited by 2
  11. 2025A New Approach to Controlling Linear Dynamical Systemscited by 2
  12. 2026Spectral Filtering for Complex Linear Dynamical Systemscited by 2
11 more
  1. 2024A least-square method for non-asymptotic identification in linear switching controlcited by 1
  2. 2024Finite Sample Analysis of Tensor Decomposition for Learning Mixtures of Linear Systemscited by 1
  3. 2025Canonical Bayesian Linear System Identificationcited by 1
  4. 2026The Power of Second Order Methods for Sequence Preconditioningcited by 1
  5. 2023Safely Learning Dynamical Systemscited by 0
  6. 2024Optimisation Strategies for Ensuring Fairness in Machine Learning: With and Without Demographicscited by 0
  7. 2025Near-optimal Rank Adaptive Inference of High Dimensional Matricescited by 0
  8. 2025Symmetric Linear Dynamical Systems are Learnable from Few Observationscited by 0
  9. 2026Online Learning for Supervisory Switching Controlcited by 0
  10. 2026Two-Layer Linear Auto-Regressive Models Estimate Latent Statescited by 0
  11. 2026Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectorycited by 0