### Abstract

Identification of a linear time-invariant dynamical system from partialobservations is a fundamental problem in control theory. A natural question ishow to do so with non-asymptotic statistical rates depending on the inherentdimensionality (order) $d$ of the system, rather than on the sufficient rolloutlength or on $\frac1{1-\rho(A)}$, where $\rho(A)$ is the spectral radius of thedynamics matrix. We develop the first algorithm that given a single trajectoryof length $T$ with gaussian observation noise, achieves a near-optimal rate of$\widetilde O\left(\sqrt\frac{d}{T}\right)$ in $\mathcal{H}_2$ error for thelearned system. We also give bounds under process noise and improved bounds forlearning a realization of the system. Our algorithm is based on low-rankapproximation of Hankel matrices of geometrically increasing sizes.