Finite Sample Analysis of Stochastic System Identification
This work addresses finite sample guarantees for system identification, which is incremental as it applies modern statistical tools to a classical control theory problem.
The paper tackles the problem of estimating parameters of a linear stochastic system from a finite trajectory of output measurements, providing non-asymptotic bounds that show estimation errors decrease at a rate of 1/√N, even for marginally stable systems.
In this paper, we analyze the finite sample complexity of stochastic system identification using modern tools from machine learning and statistics. An unknown discrete-time linear system evolves over time under Gaussian noise without external inputs. The objective is to recover the system parameters as well as the Kalman filter gain, given a single trajectory of output measurements over a finite horizon of length $N$. Based on a subspace identification algorithm and a finite number of $N$ output samples, we provide non-asymptotic high-probability upper bounds for the system parameter estimation errors. Our analysis uses recent results from random matrix theory, self-normalized martingales and SVD robustness, in order to show that with high probability the estimation errors decrease with a rate of $1/\sqrt{N}$. Our non-asymptotic bounds not only agree with classical asymptotic results, but are also valid even when the system is marginally stable.