Symmetric Linear Dynamical Systems are Learnable from Few Observations

We consider the problem of learning the parameters of a N-dimensional stochastic linear dynamics under both full and partial observations from a single trajectory of time T. We introduce and analyze a new estimator that achieves a small maximum element-wise error on the recovery of symmetric dynamic matrices using only T=O(\log N) observations, irrespective of whether the matrix is sparse or dense. This estimator is based on the method of moments and does not rely on problem-specific regularization. This is especially important for applications such as structure discovery.