Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples

• URL: http://arxiv.org/abs/2010.04015v1
• Date: Thu, 8 Oct 2020 14:23:48 GMT
• Title: Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples
• Authors: Salar Fattahi
• Abstract summary: We study the problem of learning partially observed linear dynamical systems from a single sample trajectory. Our result significantly improves the sample complexity of learning partially observed linear dynamical systems.
• Score: 4.7464518249313805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 respect to 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 will remedy this undesirable dependency on the system dimension by introducing an $\ell_1$-regularized estimation method that can accurately estimate the Markov parameters of the system, provided that the number of samples scale 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. Traditionally, the $\ell_1$-regularized estimators have been used to promote sparsity in the estimated parameters. By resorting to the notion of "weak sparsity", we show that, irrespective of the true sparsity of the system, a similar regularized estimator can be used to reduce the sample complexity of learning partially observed linear systems, provided that the true system is inherently stable.

Related papers

• Learning Controlled Stochastic Differential Equations [61.82896036131116]
  This work proposes a novel method for estimating both drift and diffusion coefficients of continuous, multidimensional, nonlinear controlled differential equations with non-uniform diffusion. We provide strong theoretical guarantees, including finite-sample bounds for (L2), (Linfty), and risk metrics, with learning rates adaptive to coefficients' regularity. Our method is available as an open-source Python library.
  arXiv  Detail & Related papers  (2024-11-04T11:09:58Z)
• A least-square method for non-asymptotic identification in linear switching control [17.938732931331064]
  It is known that the underlying partially-observed linear dynamical system lies within a finite collection of known candidate models. We characterize the finite-time sample complexity of this problem by leveraging recent advances in the non-asymptotic analysis of linear least-square methods. We propose a data-driven switching strategy that identifies the unknown parameters of the underlying system.
  arXiv  Detail & Related papers  (2024-04-11T20:55:38Z)
• Identifiability and Asymptotics in Learning Homogeneous Linear ODE Systems from Discrete Observations [114.17826109037048]
  Ordinary Differential Equations (ODEs) have recently gained a lot of attention in machine learning. theoretical aspects, e.g., identifiability and properties of statistical estimation are still obscure. This paper derives a sufficient condition for the identifiability of homogeneous linear ODE systems from a sequence of equally-spaced error-free observations sampled from a single trajectory.
  arXiv  Detail & Related papers  (2022-10-12T06:46:38Z)
• Finite Sample Identification of Bilinear Dynamical Systems [29.973598501311233]
  We show how to estimate the unknown bilinear system up to a desired accuracy with high probability. Our sample complexity and statistical error rates are optimal in terms of the trajectory length, the dimensionality of the system and the input size.
  arXiv  Detail & Related papers  (2022-08-29T22:34:22Z)
• Learning to Control Linear Systems can be Hard [19.034920102339573]
  We study the statistical difficulty of learning to control linear systems. We prove that learning complexity can be at most exponential with the controllability index, that is the degree of underactuation.
  arXiv  Detail & Related papers  (2022-05-27T15:07:30Z)
• Large-Scale System Identification Using a Randomized SVD [4.567810220723372]
  We show that an approximate matrix factorization can replace the standard SVD in the realization algorithm. This is the only method capable of producing a model.
  arXiv  Detail & Related papers  (2021-09-06T19:25:15Z)
• Supervised DKRC with Images for Offline System Identification [77.34726150561087]
  Modern dynamical systems are becoming increasingly non-linear and complex. There is a need for a framework to model these systems in a compact and comprehensive representation for prediction and control. Our approach learns these basis functions using a supervised learning approach.
  arXiv  Detail & Related papers  (2021-09-06T04:39:06Z)
• Linear Systems can be Hard to Learn [12.834033463883085]
  Statistically easy to learn linear system classes have sample complexity that is with the system dimension. Statistically hard to learn linear system classes have worst-case sample complexity that is at least exponential with the system dimension.
  arXiv  Detail & Related papers  (2021-04-02T15:58:30Z)
• Controlling nonlinear dynamical systems into arbitrary states using machine learning [77.34726150561087]
  We propose a novel and fully data driven control scheme which relies on machine learning (ML) Exploiting recently developed ML-based prediction capabilities of complex systems, we demonstrate that nonlinear systems can be forced to stay in arbitrary dynamical target states coming from any initial state. Having this highly flexible control scheme with little demands on the amount of required data on hand, we briefly discuss possible applications that range from engineering to medicine.
  arXiv  Detail & Related papers  (2021-02-23T16:58:26Z)
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms [74.17312533172291]
  We describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding) We then explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation)
  arXiv  Detail & Related papers  (2020-12-12T00:01:10Z)
• Active Learning for Nonlinear System Identification with Guarantees [102.43355665393067]
  We study a class of nonlinear dynamical systems whose state transitions depend linearly on a known feature embedding of state-action pairs. We propose an active learning approach that achieves this by repeating three steps: trajectory planning, trajectory tracking, and re-estimation of the system from all available data. We show that our method estimates nonlinear dynamical systems at a parametric rate, similar to the statistical rate of standard linear regression.
  arXiv  Detail & Related papers  (2020-06-18T04:54:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.