Nonconvex Linear System Identification with Minimal State Representation

Uday Kiran Reddy Tadipatri, Benjamin D. Haeffele, Joshua Agterberg, Ingvar Ziemann, René Vidal · 2025

Read Nonconvex Linear System Identification with Minimal State Representation by Uday Kiran Reddy Tadipatri, Benjamin D. Haeffele, Joshua Agterberg, Ingvar Ziemann, René Vidal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18791.txt.

Introduction

Uday Kiran Reddy Tadipatri and four co-authors find faster routes to identifying simple linear systems from data, in a 2025 paper. Engineers often need a compact model of a system from limited observations and inputs. The standard approach minimizes a matrix rank surrogate, but it needs many expensive decompositions along the way.

The authors offer two nonconvex reformulations. One factors the data matrix directly, making the optimization cheap. The other optimizes over the system parameters themselves, for systems with well-behaved structure. Surprisingly, they prove these nonconvex problems still reach the global optimum in polynomial time. Working directly with parameters also needs fewer samples, and the requirement does not grow with trajectory length as the older method's does. Tests on synthetic data backed the theory. The work aims to make low-order system identification both quicker and statistically leaner.

Catalog record

CREATORUday Kiran Reddy Tadipatri, Benjamin D. Haeffele, Joshua Agterberg, Ingvar Ziemann, René Vidal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18791

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Nonconvex Linear System Identification with Minimal State Representation Uday Kiran Reddy Tadipatri, Benjamin D. Haeffele, Joshua Agterberg, Ingvar Ziemann, René Vidal Abstract 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. keywords System Identification, Hankel rank minimization, Sample Complexity. 1 Introduction We consider the linear time-invariant system ( LS ) with time t\in\mathbb{N} , {\mathbf{x}}_{t}\in{\mathbb{R}}^{n_{x}} as hidden states, {\mathbf{u}}_{t}\in{\mathbb{R}}^{n_{u}} as control inputs, {\mathbf{y}}_{t}\in{\mathbb{R}}^{n_{y}} as outputs, \zeta_{t}\in{\mathbb{R}}^{n_{y}} as output noise, and system parameters (A\in{\mathbb{R}}^{n_{x}\times n_{x}} , B\in{\mathbb{R}}^{n_{x}\times n_{u}} , C\in{\mathbb{R}}^{n_{y}\times n_{x}} , D\in{\mathbb{R}}^{n_{y}\times n_{u}}) described as \begin{split}&{\mathbf{x}}_{t+1}=A{\mathbf{x}}_{t}+B{\mathbf{u}}_{t};{\mathbf{x}}_{1}=0,\\ &{\mathbf{y}}_{t}=C{\mathbf{x}}_{t}+D{\mathbf{u}}_{t}+\zeta_{t}.\end{split} (LS) Linear System IDentification (SysID) aims to estimate these parameters (A , B, C, D) using finite rollouts with finite length trajectories, \{({\mathbf{u}}_{t}^{i},{\mathbf{y}}_{t}^{i})_{t=1}^{2L+2}\}_{i=1}^{N} . However, the true system order or state dimension n_{x} is typically unknown. It is of practical interest to find systems that are minimal order as such models provide faster response times, simplified control designs, and improved robustness, while mitigating overfitting during the learning phase. This task can be formulated as a dimension minimization problem under an L_{2} norm constraint (see Program ( P0 )). However, solving this problem is known to be NP-HARD ( Vandenberghe and Boyd, 1996 ) . In classical linear system theory, the order of the system is determined by the rank of the Hankel matrix constructed from the Markov parameters (CB,CAB,\dots,CA^{2L+1}B) ( Sontag, 2013 , Corollary 6.5.7) . Convex relaxations, such as minimizing the Hankel nuclear norm instead of the rank, have been proposed to make this problem computationally tractable ( Fazel et al., 2003 ) . However, this presents two key challenges: (i) Computational complexity : The number of parameters scales linearly with the trajectory length L , making nuclear norm minimization increasingly difficult. (ii) Statistical inefficiency : The high dimensionality leads to worse statistical error rates and larger sample complexity requirements ( Oymak and Ozay, 2019 ) . In the literature on matrix sensing, nuclear norm minimization is tackled via nonconvex reparameterization using its variational form with Frobenius norms ( Burer and Monteiro, 2003 ) . This reformulation enables the use of efficient first-order optimization methods, such as gradient descent and Nesterov acceleration ( Nesterov, 1983 ) , which converge in \mathcal{O}(1/T) , and \mathcal{O}(1/T^{2}) , respectively, where T is the number of iterations. In contrast, direct nuclear norm minimization often requires computing proximal operators ( Parikh et al., 2014 ) that depend on SVD, making it less computationally efficient. In this work, we propose two reformulations, the first of which is Hankel nuclear norm minimization for SysID (see Program ( P1 )) using the BM factorization ( Burer and Monteiro, 2003 ) . Despite being nonconvex, this formulation eliminates the need for frequent SVD computations, significantly enhancing computational efficiency, and can still be provably globally optimized in polynomial time. While this first reformulation offers clear advantages in terms of optimization efficiency, the statistical error rates and sample complexities remain comparable to those of Hankel nuclear norm minimization. In particular, the statistical error rates scale with trajectory length, despite the number of system parameters remaining constant. Our second reformulation (see Program ( P2 )) proposes a method of SysID of a real, diagonalizable system where we perform optimization directly over the system parameters space (A,B,C,D) with a structured regularization similar to an atomic norm decomposition. Although this reformulation is also nonconvex, we show that it can be efficiently optimized to global optimality. Furthermore, this approach achieves improved statistical error rates and reduced sample complexity compared to existing Hankel nuclear norm minimization heuristics. Contributions. Our key contributions are as follows: 1. Nonconvex Relaxations for low-order SysID. We propose two nonconvex reformulations (i) for general linear systems via BM re-parametrization ( P1 ) of the Hankel matrix, (ii) by directly optimizing over system parameters ( P2 ), restricted to real, diagonalizable systems. These nonconvex problems are first of their kind and serve as relaxations to the NP-HARD problem ( P0 ). 2. Global Optimality Guarantees. We provide guarantees of global optimality for the two nonconvex reformulations when they are solved using first-order optimization procedures. Furthermore, we affirm that these nonconvex problems can be solved in polynomial time. The second reformulation overcomes the quadratic dependency on trajectory length in the computational efficiency of existing methods. 3. Statistical Error Rates and Sample Complexities. We provide statistical error rates and sample complexities for both the reformulations while the first reformulation scales poorly compared to the second due to its linear dependency on trajectory length. 4. Numerical evidence. We propose algorithms to tackle these nonconvex programs, provide numerical simulations that corroborate our theoretical insights. Under a fixed compute budget, our algorithms outperform existing methods. These results highlight that for real, diagonalizable systems the reformulation ( P2 ) achieves both superior statistical efficiency and reduced sample complexity compared to ( P1 ), Sun et al. (2022) , and Lee (2022) . Organization. First, in § 2 we introduce the problem and mathematical formulations. Next, we move onto § 3 where we present optimality certificates for the nonconvex formulations. Then, in § 4 we present statistical error rates and sample complexities for each of the formulations. Later, we move to § 5 that presents numerical experimentation and comparison with existing methods. Finally, we conclude and discuss the future work in § 6 . Further related works and proofs for all the mathematical statements can be found in Appendix of our arXiv version. Notation. For a matrix A , [A]_{i_{1}:i_{2},j_{1}:j_{2}} denotes its submatrix from rows i_{1} – i_{2} and columns j_{1} – j_{2} ; [[A_{i,j}]_{i\in\mathcal{I}}]_{j\in\mathcal{J}} stacks blocks A_{i,j} row- and column-wise over \mathcal{I} and \mathcal{J} . The superscript \dagger denotes the adjoint for operators and the Moore–Penrose pseudoinverse for matrices. The inequality f(x)\gtrsim g(x) or f(x)\geq\mathcal{O}(g(x)) means there exists a positive constant c such that f(x)\geq cg(x) for all x . For some \alpha>0 , (\ln x)^{\alpha} is denoted as {\sf polylog}(x) , and \tilde{\mathcal{O}}(x) denotes \mathcal{O}(x\cdot{\sf polylog}(x)) . 2 Problem Formulation Given a noisy linear time-invariant system ( LS ), we are interested in special approximation of outputs \{{\mathbf{y}}_{t}\}_{t=1}^{2L+2} for given inputs \{{\mathbf{u}}_{t}\}_{t=1}^{2L+2} that has low-order, or smaller state dimension, n_{x} . Formally, define impulse response 1 1 1 Due to the trivial estimation of D we often omit its dependency in the impulse response and

Read the complete text