Optimal Centered Active Excitation in Linear System Identification

Kaito Ito; Alexandre Proutiere

math.OCApr 7, 2026

Optimal Centered Active Excitation in Linear System Identification

Authors: Kaito Ito, Alexandre Proutiere

Organizations: Department of Information Physics and Computing, The University of Tokyo, Tokyo 113-8654, Japan · Division of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Stockholm 114 28, Sweden

Abstract

We propose an active learning algorithm for linear system identification with optimal centered noise excitation. Notably, our algorithm, based on ordinary least squares and semidefinite programming, attains the minimal sample complexity while allowing for efficient computation of an estimate of a system matrix. More specifically, we first establish lower bounds of the sample complexity for any active learning algorithm to attain the prescribed accuracy and confidence levels. Next, we derive a sample complexity upper bound of the proposed algorithm, which matches the lower bound for any algorithm up to universal factors. Our tight bounds are easy to interpret and explicitly show their dependence on the system parameters such as the state dimension.

Figures & tables

Fig. 1 : Number of samples and the estimation error, where $n_{x}=4$ , $B=I$ , $\bar{u}=1$ , $\sigma_{w}=0.1$ , and $A$ is the Jordan block with diagonal entry $0.8$ .

Explore similar work

CLT-Optimal Parameter Error Bounds for Linear System Identification
Apr 23, 2026Yichen Zhou, Stephen TuSystem Identification Least Squares
Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, California, USA.
Achieving $\widetilde{O}(1/ε)$ Sample Complexity for Bilinear Systems Identification under Bounded Noises
Mar 21, 2026Hongyu Yi, Chenbei Lu, Jing YuSystem Identification Optimal Sample Complexity
Department of Electrical and Computer Engineering, University of Washington, Seattle, WA, USA. · Cornell University AI for Science Institute, Cornell University, Ithaca, NY, USA.
Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory
Sep 30, 2026Xiaomian Yang, Sungho ShinOptimal Sample Complexity Least Squares
Department of Chemical Engineering Massachusetts Institute of Technology Cambridge, MA 02139

Apr 23, 2026, stat.MLJ/K move · Enter open · S save

CLT-Optimal Parameter Error Bounds for Linear System Identification

Yichen Zhou, Stephen Tu

Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, California, USA.

System Identification Least Squares

Open paper AskPDF arXiv

There has been remarkable progress over the past decade in establishing finite-sample, non-asymptotic bounds on recovering unknown system parameters from observed system behavior. Surprisingly, however, we show that the current state-of-the-art bounds do not accurately capture the statistical complexity of system identification, even in the most fundamental setting of estimating a discrete-time linear dynamical system (LDS) via ordinary least-squares regression (OLS). Specifically, we utilize asymptotic normality to identify classes of problem instances for which current bounds overstate the squared parameter error, in both spectral and Frobenius norm, by a factor of the state-dimension of the system. Informed by this discrepancy, we then sharpen the OLS parameter error bounds via a novel second-order decomposition of the parameter error, where crucially the lower-order term is a matrix-valued martingale that we show correctly captures the CLT scaling. From our analysis we obtain finite-sample bounds for both (i) stable systems and (ii) the many-trajectories setting that match the instance-specific optimal rates up to constant factors in Frobenius norm, and polylogarithmic state-dimension factors in spectral norm.

Abstract

Explore similar work

CLT-Optimal Parameter Error Bounds for Linear System Identification

Achieving O~(1/ε)\widetilde{O}(1/ε)O(1/ε) Sample Complexity for Bilinear Systems Identification under Bounded Noises

Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory

Achieving $\widetilde{O}(1/ε)$ Sample Complexity for Bilinear Systems Identification under Bounded Noises