  Linear dynamical systems are the foundational statistical model upon which
control theory is built. Both the celebrated Kalman filter and the linear
quadratic regulator require knowledge of the system dynamics to provide
analytic guarantees. Naturally, learning the dynamics of a linear dynamical
system from linear measurements has been intensively studied since Rudolph
Kalman's pioneering work in the 1960's. Towards these ends, we provide the
first polynomial time algorithm for learning a linear dynamical system from a
polynomial length trajectory up to polynomial error in the system parameters
under essentially minimal assumptions: observability, controllability, and
marginal stability. Our algorithm is built on a method of moments estimator to
directly estimate Markov parameters from which the dynamics can be extracted.
Furthermore, we provide statistical lower bounds when our observability and
controllability assumptions are violated.
