System identification from partial samples: Non-asymptotic analysis

The problem of learning the parameters of a vector autoregressive (VAR) process from partial random measurements is considered. This setting arises due to missing data or data corrupted by multiplicative bounded noise. We present an estimator of the covariance matrix of the evolving state-vector from its partial noisy observations. We analyze the non-asymptotic behavior of this estimator and provide an upper bound for its convergence rate. This expression shows that the effect of partial observations on the first order convergence rate is equivalent to reducing the sample size to the average number of observations viewed, implying that our estimator is order-optimal. We then present and analyze two techniques to recover the VAR parameters from the estimated covariance matrix applicable in dense and in sparse high-dimensional settings. We demonstrate the applicability of our estimation techniques in joint state and system identification of a stable linear dynamic system with random inputs.