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/08/06)
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.
|
|
dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
| |
Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
|
|