Title: Learning Linear Dynamical Systems via Spectral Filtering,
Abstract: We present an efficient and practical algorithm for the online prediction of
discrete-time linear dynamical systems with a symmetric transition matrix. We
circumvent the non-convex optimization problem using improper learning:
carefully overparameterize the class of LDSs by a polylogarithmic factor, in
exchange for convexity of the loss functions. From this arises a
polynomial-time algorithm with a near-optimal regret guarantee, with an
analogous sample complexity bound for agnostic learning. Our algorithm is based
on a novel filtering technique, which may be of independent interest: we
convolve the time series with the eigenvectors of a certain Hankel matrix.