Papers Published
Abstract:
Identification of a linear time-invariant dynamical system from partial
observations is a fundamental problem in control theory. Particularly
challenging are systems exhibiting long-term memory. A natural question is how
learn such systems with non-asymptotic statistical rates depending on the
inherent dimensionality (order) $d$ of the system, rather than on the possibly
much larger memory length. We propose an algorithm that given a single
trajectory of length $T$ with gaussian observation noise, learns the system
with a near-optimal rate of $\widetilde O\left(\sqrt\frac{d}{T}\right)$ in
$\mathcal{H}_2$ error, with only logarithmic, rather than polynomial dependence
on memory length. We also give bounds under process noise and improved bounds
for learning a realization of the system. Our algorithm is based on multi-scale
low-rank approximation: SVD applied to Hankel matrices of geometrically
increasing sizes. Our analysis relies on careful application of concentration
bounds on the Fourier domain -- we give sharper concentration bounds for sample
covariance of correlated inputs and for $\mathcal H_\infty$ norm estimation,
which may be of independent interest.