Learning linear dynamical systems under convex constraints

We consider the problem of finite-time identification of linear dynamical systems from T samples of a single trajectory. Recent results have predominantly focused on the setup where either no structural assumption is made on the system matrix A^* \in \mathbb{R}^{n \times n}, or specific structural assumptions (e.g. sparsity) are made on A^. We assume prior structural information on A^ is available, which can be captured in the form of a convex set K containing A^. For the solution of the ensuing constrained least squares estimator, we derive non-asymptotic error bounds in the Frobenius norm that depend on the local size of K at A^. To illustrate the usefulness of these results, we instantiate them for four examples, namely when (i) A^* is sparse and K is a suitably scaled \ell_1 ball; (ii) K is a subspace; (iii) K consists of matrices each of which is formed by sampling a bivariate convex function on a uniform n \times n grid (convex regression); (iv) K consists of matrices each row of which is formed by uniform sampling (with step size 1/T) of a univariate Lipschitz function. In all these situations, we show that A^* can be reliably estimated for values of T much smaller than what is needed for the unconstrained setting.