Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples

Salar Fattahi
Proceedings of the 3rd Conference on Learning for Dynamics and Control, PMLR 144:60-72, 2021.

Abstract

In this work, we study the problem of learning partially observed linear dynamical systems from a single sample trajectory. A major practical challenge in the existing system identification methods is the undesirable dependency of their required sample size on the system dimension: roughly speaking, they presume and rely on sample sizes that scale linearly with the system dimension. Evidently, in high-dimensional regime where the system dimension is large, it may be costly, if not impossible, to collect as many samples from the unknown system. In this paper, we introduce an regularized estimator that can accurately estimate the Markov parameters of the system, provided that the number of samples scale poly-logarithmically with the system dimension. Our result significantly improves the sample complexity of learning partially observed linear dynamical systems: it shows that the Markov parameters of the system can be learned in the high-dimensional setting, where the number of samples is significantly smaller than the system dimension.

Cite this Paper

BibTeX
@InProceedings{pmlr-v144-fattahi21a, title = {Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples}, author = {Fattahi, Salar}, booktitle = {Proceedings of the 3rd Conference on Learning for Dynamics and Control}, pages = {60--72}, year = {2021}, editor = {Jadbabaie, Ali and Lygeros, John and Pappas, George J. and A. Parrilo, Pablo and Recht, Benjamin and Tomlin, Claire J. and Zeilinger, Melanie N.}, volume = {144}, series = {Proceedings of Machine Learning Research}, month = {07 -- 08 June}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v144/fattahi21a/fattahi21a.pdf}, url = {https://proceedings.mlr.press/v144/fattahi21a.html}, abstract = {In this work, we study the problem of learning partially observed linear dynamical systems from a single sample trajectory. A major practical challenge in the existing system identification methods is the undesirable dependency of their required sample size on the system dimension: roughly speaking, they presume and rely on sample sizes that scale linearly with the system dimension. Evidently, in high-dimensional regime where the system dimension is large, it may be costly, if not impossible, to collect as many samples from the unknown system. In this paper, we introduce an regularized estimator that can accurately estimate the Markov parameters of the system, provided that the number of samples scale poly-logarithmically with the system dimension. Our result significantly improves the sample complexity of learning partially observed linear dynamical systems: it shows that the Markov parameters of the system can be learned in the high-dimensional setting, where the number of samples is significantly smaller than the system dimension.} }
Endnote
%0 Conference Paper %T Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples %A Salar Fattahi %B Proceedings of the 3rd Conference on Learning for Dynamics and Control %C Proceedings of Machine Learning Research %D 2021 %E Ali Jadbabaie %E John Lygeros %E George J. Pappas %E Pablo A. Parrilo %E Benjamin Recht %E Claire J. Tomlin %E Melanie N. Zeilinger %F pmlr-v144-fattahi21a %I PMLR %P 60--72 %U https://proceedings.mlr.press/v144/fattahi21a.html %V 144 %X In this work, we study the problem of learning partially observed linear dynamical systems from a single sample trajectory. A major practical challenge in the existing system identification methods is the undesirable dependency of their required sample size on the system dimension: roughly speaking, they presume and rely on sample sizes that scale linearly with the system dimension. Evidently, in high-dimensional regime where the system dimension is large, it may be costly, if not impossible, to collect as many samples from the unknown system. In this paper, we introduce an regularized estimator that can accurately estimate the Markov parameters of the system, provided that the number of samples scale poly-logarithmically with the system dimension. Our result significantly improves the sample complexity of learning partially observed linear dynamical systems: it shows that the Markov parameters of the system can be learned in the high-dimensional setting, where the number of samples is significantly smaller than the system dimension.
APA
Fattahi, S.. (2021). Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples. Proceedings of the 3rd Conference on Learning for Dynamics and Control, in Proceedings of Machine Learning Research 144:60-72 Available from https://proceedings.mlr.press/v144/fattahi21a.html.

Related Material