Learning structured linear dynamical systems from missing observations

We consider the problem of learning structured linear dynamical systems over convex sets K, where only a small subset of the observations are available at each time point. An estimator which minimizes a bias-corrected, potentially non-convex objective function is proposed. Non-asymptotic bounds are obtained for the statistical error, which depend on the local complexity of K, the trajectory length T, and the sub-sampling probability p. Convergence of the projected gradient descent algorithm is also established. The general theory is applied to settings where (i) K is a subspace, (ii) K is the set of bi-isotonic matrices, and (iii) K is the set of matrices whose rows are formed by sampling Lipschitz functions. We show meaningful recovery of the transition matrix is possible for values of T much smaller than what is required in the unconstrained case, and for p = o(1).