# Large-Scale System Identification Using a Randomized SVD

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 6 Sep 2021.

## Builds on (most cited first, 15 of 15)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020)
- [Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification](https://mlsanity.com/paper/1707.04791/) (2017)
- [Faster Matrix Completion Using Randomized SVD](https://mlsanity.com/paper/1810.06860/) (2018)
- [Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory](https://mlsanity.com/paper/2102.11822/) (2021)

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

- [FedSysID: A Federated Approach to Sample-Efficient System Identification](https://mlsanity.com/paper/2211.14393/) (2022)
- [Learning Linear Models Using Distributed Iterative Hessian Sketching](https://mlsanity.com/paper/2112.04101/) (2021)

## Abstract (arXiv)

Learning a dynamical system from input/output data is a fundamental task in the control design pipeline. In the partially observed setting there are two components to identification: parameter estimation to learn the Markov parameters, and system realization to obtain a state space model. In both sub-problems it is implicitly assumed that standard numerical algorithms such as the singular value decomposition (SVD) can be easily and reliably computed. When trying to fit a high-dimensional model to data, for example in the cyber-physical system setting, even computing an SVD is intractable. In this work we show that an approximate matrix factorization obtained using randomized methods can replace the standard SVD in the realization algorithm while maintaining the non-asymptotic (in data-set size) performance and robustness guarantees of classical methods. Numerical examples illustrate that for large system models, this is the only method capable of producing a model.