# Nonconvex Linear System Identification with Minimal State Representation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 26 Apr 2025.

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

- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Deep networks for system identification: a Survey](https://mlsanity.com/paper/2301.12832/) (2023)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [Learning from many trajectories](https://mlsanity.com/paper/2203.17193/) (2022)
- [Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications](https://mlsanity.com/paper/1708.07850/) (2017)
- [Improved rates for prediction and identification of partially observed linear dynamical systems](https://mlsanity.com/paper/2011.10006/) (2020)
- [Regularized linear system identification using atomic, nuclear and kernel-based norms: the role of the stability constraint](https://mlsanity.com/paper/1507.00564/) (2015)
- [Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss](https://mlsanity.com/paper/2402.05928/) (2024)
- [Convex relaxations of structured matrix factorizations](https://mlsanity.com/paper/1309.3117/) (2013)
- [A Convex Relaxation Approach to Generalization Analysis for Parallel Positively Homogeneous Networks](https://mlsanity.com/paper/2411.02767/) (2024)

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

- [Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weights](https://mlsanity.com/paper/2604.17578/) (2026)
- [Two-Layer Linear Auto-Regressive Models Estimate Latent States](https://mlsanity.com/paper/2606.12691/) (2026)

## Abstract (arXiv)

Low-order linear System IDentification (SysID) addresses the challenge of estimating the parameters of a linear dynamical system from finite samples of observations and control inputs with minimal state representation. Traditional approaches often utilize Hankel-rank minimization, which relies on convex relaxations that can require numerous, costly singular value decompositions (SVDs) to optimize. In this work, we propose two nonconvex reformulations to tackle low-order SysID (i) Burer-Monterio (BM) factorization of the Hankel matrix for efficient nuclear norm minimization, and (ii) optimizing directly over system parameters for real, diagonalizable systems with an atomic norm style decomposition. These reformulations circumvent the need for repeated heavy SVD computations, significantly improving computational efficiency. Moreover, we prove that optimizing directly over the system parameters yields lower statistical error rates, and lower sample complexities that do not scale linearly with trajectory length like in Hankel-nuclear norm minimization. Additionally, while our proposed formulations are nonconvex, we provide theoretical guarantees of achieving global optimality in polynomial time. Finally, we demonstrate algorithms that solve these nonconvex programs and validate our theoretical claims on synthetic data.