Math @ Duke

Publications [#361426] of Holden Lee
Papers Published
 Lee, H, Improved rates for prediction and identification of partially observed
linear dynamical systems,
Alt 2022
(November, 2020)
(last updated on 2022/05/22)
Abstract: Identification of a linear timeinvariant dynamical system from partial
observations is a fundamental problem in control theory. Particularly
challenging are systems exhibiting longterm memory. A natural question is how
learn such systems with nonasymptotic 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 nearoptimal 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 multiscale
lowrank 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

