Finite-time Identification of Stable Linear Systems Optimality of the Least-Squares Estimator

We present a new finite-time analysis of the estimation error of the Ordinary Least Squares (OLS) estimator for stable linear time-invariant systems. We characterize the number of observed samples (the length of the observed trajectory) sufficient for the OLS estimator to be (epsilon, delta)-PAC, i.e., to yield an estimation error less than epsilon with probability at least 1-delta. We show that this number matches existing sample complexity lower bounds [1], [2] up to universal multiplicative factors (independent of (epsilon, delta) and of the system). This paper hence establishes the optimality of the OLS estimator for stable systems, a result conjectured in [1]. Our analysis of the performance of the OLS estimator is simpler, sharper, and easier to interpret than existing analyses. It relies on new concentration results for the covariates matrix.