# System Identification via Nuclear Norm Regularization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 64 references that are in the map.
- First posted on arXiv 30 Mar 2022.

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

- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [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)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Learning nonlinear dynamical systems from a single trajectory](https://mlsanity.com/paper/2004.14681/) (2020)
- [Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems](https://mlsanity.com/paper/2002.08538/) (2020)
- [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [Safely Learning to Control the Constrained Linear Quadratic Regulator](https://mlsanity.com/paper/1809.10121/) (2018)
- [Active Learning for Identification of Linear Dynamical Systems](https://mlsanity.com/paper/2002.00495/) (2020)
- [Learning the Linear Quadratic Regulator from Nonlinear Observations](https://mlsanity.com/paper/2010.03799/) (2020)
- [Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification](https://mlsanity.com/paper/1707.04791/) (2017)
- [Stochastic Gradient Descent Learns State Equations with Nonlinear Activations](https://mlsanity.com/paper/1809.03019/) (2018)
- [Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds](https://mlsanity.com/paper/2111.07018/) (2021)
- [Nonparametric Finite Time LTI System Identification](https://mlsanity.com/paper/1902.01848/) (2019)
- [Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples](https://mlsanity.com/paper/2010.04015/) (2020)
- [Convex Programming for Estimation in Nonlinear Recurrent Models](https://mlsanity.com/paper/1908.09915/) (2019)
- [Estimation with Norm Regularization](https://mlsanity.com/paper/1505.02294/) (2015)
- [Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction](https://mlsanity.com/paper/1503.02893/) (2015)
- [Mode Clustering for Markov Jump Systems](https://mlsanity.com/paper/1910.02193/) (2019)
- [Nonlinear System Identification with Prior Knowledge of the Region of Attraction](https://mlsanity.com/paper/2003.12330/) (2020)
- [Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory](https://mlsanity.com/paper/2102.11822/) (2021)
- [Certainty Equivalent Quadratic Control for Markov Jump Systems](https://mlsanity.com/paper/2105.12358/) (2021)
- [Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information](https://mlsanity.com/paper/1312.0641/) (2013)
- [Separation-Free Super-Resolution from Compressed Measurements is Possible: an Orthonormal Atomic Norm Minimization Approach](https://mlsanity.com/paper/1711.01396/) (2017)
- [The achievable performance of convex demixing](https://mlsanity.com/paper/1309.7478/) (2013)

## Abstract (arXiv)

This paper studies the problem of identifying low-order linear systems via Hankel nuclear norm regularization. Hankel regularization encourages the low-rankness of the Hankel matrix, which maps to the low-orderness of the system. We provide novel statistical analysis for this regularization and carefully contrast it with the unregularized ordinary least-squares (OLS) estimator. Our analysis leads to new bounds on estimating the impulse response and the Hankel matrix associated with the linear system. We first design an input excitation and show that Hankel regularization enables one to recover the system using optimal number of observations in the true system order and achieve strong statistical estimation rates. Surprisingly, we demonstrate that the input design indeed matters, by showing that intuitive choices such as i.i.d. Gaussian input leads to provably sub-optimal sample complexity. To better understand the benefits of regularization, we also revisit the OLS estimator. Besides refining existing bounds, we experimentally identify when regularized approach improves over OLS: (1) For low-order systems with slow impulse-response decay, OLS method performs poorly in terms of sample complexity, (2) Hankel matrix returned by regularization has a more clear singular value gap that ease identification of the system order, (3) Hankel regularization is less sensitive to hyperparameter choice. Finally, we establish model selection guarantees through a joint train-validation procedure where we tune the regularization parameter for near-optimal estimation.