(644a) Sample Complexity Bounds for Linear System Identification without Sub-Gaussianity and Iid Assumptions

System identification (SID) is a classical method used to determine the dynamics of a physical system based on its observations on the system. Various SID methods, including autoregressive models with exogenous input (ARX) and subspace identification approaches, are commonly employed in practical controller design. Typical SID techniques, such as subspace identification, rely on least-squares estimation of the Markov parameters, which are then used to form dynamical models in state-space representation. Notable examples of these methods include canonical variate analysis (CVA), MOESP, and N4SID. SID plays a crucial role in various applications, including chemical process control, robotics, and power system control [5,6]. The identification of system dynamics from observation is inherently subject to random system noises. Consequently, it is essential to rigorously analyze the error associated with the accuracy of the identified models in relation to sample size and varying conditions to effectively tackle SID challenges in real-world engineering scenarios. These analysis is often referred to as sample complexity analysis and has been a central topic in the field of system identification. Due to the surge in the interest of data-driven approaches for control, sample complexity analysis has gained significant renewed attention in recent years [7,8,9,10,11,12].

Recent works in sample complexity analysis have focused on establishing non-asymptotic error bounds (applicable for all regimes of sample size) for least-squares estimation for linear systems [7,8], as well as for subspace identification [9,10,11,12]. This analysis technique establishes high-probability error bound expresed in terms of sample size and various system parameters. While these studies have established tight sample complexity bounds for standard linear system identification problems, they impose restrictive assumptions on the input uncertainty distributions, such as mean-zero i.i.d. Gaussian [9], positive definite covariance [9,10,11], or sub-Gaussian noise [10,11]. However, some of these assumptions are restrictive, limiting the scope of the problems that can be handled by these analytical results. For example, PRBS input is standard in many practical SID approaches, but PRBS signals do not satisfy the mean-zero i.i.d. assumption. Furthermore, rank-deficient covariance matrix may arise when only a part of the system is subject to uncertainty. Lastly, the system may be subject to uncertainty with heavy-tailed distributions that do not satify the sub-Gaussianity assumption. These limitations of the existing analyses necessitates further research on the sample complexity anlaysis under relaxed assumptions. In this context, our research seeks to bridge this gap by performing non-asymptotic sample complexity analysis for linear system identification problems focusing on the following settings: (1) pseudo-random binary signal (PRBS) input with non-zero covariance entries, (2) systems with process noise with a rank-deficient covariance matrix, and (3) dynamical systems parameterized by a small number of parameters (e.g., sparse dynamical systems).

Building upon recent studies that assumed sub-Gaussian [10,11] and sub-exponential input noise [12], we show that one can maintain a sample complexity bound of $O(1/\sqrt{T})$---the best known scaling under Gaussian noise assumptions with i.i.d. input---for PRBS signals and rank-deficient covariance matrices. Our approach is based on expressing the estimation error term using an ensemble matrix for the noise vectors, whose concentration bounds can be established based on matrix Chernoff-like inequalities [13]. Furthermore, we establish a sharper sample complexity bound for linear dynamical systems parameterized by a small number of parameters (e.g., sparse dynamical systems). In future work, we plan to apply our theoretical analysis to industry-relevant problems such as controlling chemical reactor models that are partially affected by random noise, designing a stable power system operator for flexible demand-response (which employs PRBS noise), and constructing optimal policy for grid-scale battery storage systems. Through this work, we aim to establish a more generalized theoretical framework for SID non-asymptotic sample complexity analysis that can address critical challenges across chemical engineering, computer science, and other applied engineering disciplines.

References
[1] Benben Jiang, Dexian Huang, Xiaoxiang Zhu, Fan Yang, and Richard D Braatz. Canonical variate analysis-based contributions for fault identification. J. Process Control, 26:17–25, February 2015.
[2] Benben Jiang, Xiaoxiang Zhu, Dexian Huang, and Richard D Braatz. Canonical variate analysis-based monitoring of process correlation structure using causal feature representation. J. Process Control, 32:109–116, August 2015.
[3] S Joe Qin. An overview of subspace identification. Comput. Chem. Eng., 30(10-12):1502–1513, 12 September 2006.
[4] Peter Van Overschee and Bart de Moor. N4SID* subspace algorithms for the identification of combined deterministic- stochastic systems. No. I. pp., 75:93, 1994.
[5] Ugo Rosolia, Xiaojing Zhang, and Francesco Borrelli. Data-driven predictive control for autonomous systems. Annu. Rev. Control Robot. Auton. Syst., 1(1):259–286, 28 May 2018.
[6] Laurel N Dunn. Data-Driven Decision Analysis in Electric Power Systems. PhD thesis, UC Berkeley, 2020.
[7] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Found. Comut. Math., 20(4):633–679, August 2020.
[8] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of linear system identification. arXiv [cs.LG], 22 February 2018.
[9] Samet Oymak and Necmiye Ozay. Non-asymptotic identification of LTI systems from a single trajectory. arXiv [cs.LG], 14 June 2018.
[10] Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J Pappas. Statistical learning theory for control: A finite sample perspective. arXiv [eess.SY], 12 September 2022.
[11] Ingvar Ziemann, Anastasios Tsiamis, Bruce Lee, Yassir Jedra, Nikolai Matni, and George J Pappas. A tutorial on the non-asymptotic theory of system identification. arXiv [eess.SY], 7 September 2023.
[12] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau. A new approach to learning linear dynamical systems. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 335–348, New York, NY, USA, 2 June 2023. ACM.
[13] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, England, 21 February 2019.