Improved rates for prediction and identification of partially observed linear dynamical systems

arXiv2011.10006MaRDI QIDQ6354139

Author name not available (Why is that?)

Publication date: 19 November 2020

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 $widetildeOleft(sqrtfracdTight)$ 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}_{i}nfty$ norm estimation, which may be of independent interest.

Has companion code repository: https://github.com/holdenlee/hankel-svd

This page was built for publication: Improved rates for prediction and identification of partially observed linear dynamical systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354139)