Learning Linear Dynamics from Bilinear Observations

• URL: http://arxiv.org/abs/2409.16499v1
• Date: Tue, 24 Sep 2024 23:11:47 GMT
• Title: Learning Linear Dynamics from Bilinear Observations
• Authors: Yahya Sattar, Yassir Jedra, Sarah Dean,
• Abstract summary: We consider the problem of learning a realization of a partially observed dynamical system with linear state transitions and bilinear observations. Under very mild assumptions on the process and measurement noises, we provide a finite time analysis for learning the unknown dynamics matrices.
• Score: 8.238163867581848
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of learning a realization of a partially observed dynamical system with linear state transitions and bilinear observations. Under very mild assumptions on the process and measurement noises, we provide a finite time analysis for learning the unknown dynamics matrices (up to a similarity transform). Our analysis involves a regression problem with heavy-tailed and dependent data. Moreover, each row of our design matrix contains a Kronecker product of current input with a history of inputs, making it difficult to guarantee persistence of excitation. We overcome these challenges, first providing a data-dependent high probability error bound for arbitrary but fixed inputs. Then, we derive a data-independent error bound for inputs chosen according to a simple random design. Our main results provide an upper bound on the statistical error rates and sample complexity of learning the unknown dynamics matrices from a single finite trajectory of bilinear observations.

Related papers

• Learning Linear Attention in Polynomial Time [115.68795790532289]
  We provide the first results on learnability of single-layer Transformers with linear attention. We show that linear attention may be viewed as a linear predictor in a suitably defined RKHS. We show how to efficiently identify training datasets for which every empirical riskr is equivalent to the linear Transformer.
  arXiv  Detail & Related papers  (2024-10-14T02:41:01Z)
• Unsupervised Representation Learning from Sparse Transformation Analysis [79.94858534887801]
  We propose to learn representations from sequence data by factorizing the transformations of the latent variables into sparse components. Input data are first encoded as distributions of latent activations and subsequently transformed using a probability flow model.
  arXiv  Detail & Related papers  (2024-10-07T23:53:25Z)
• Learning Linearized Models from Nonlinear Systems with Finite Data [1.6026317505839445]
  We consider the problem of identifying a linearized model when the true underlying dynamics is nonlinear. We provide a multiple trajectories-based deterministic data acquisition algorithm followed by a regularized least squares algorithm. Our error bound demonstrates a trade-off between the error due to nonlinearity and the error due to noise, and shows that one can learn the linearized dynamics with arbitrarily small error.
  arXiv  Detail & Related papers  (2023-09-15T22:58:03Z)
• Inexact iterative numerical linear algebra for neural network-based spectral estimation and rare-event prediction [0.0]
  Leading eigenfunctions of the transition operator are useful for visualization. We develop inexact iterative linear algebra methods for computing these eigenfunctions.
  arXiv  Detail & Related papers  (2023-03-22T13:07:03Z)
• Learning the Dynamics of Sparsely Observed Interacting Systems [0.6021787236982659]
  We address the problem of learning the dynamics of an unknown non-parametric system linking a target and a feature time series. By leveraging the rich theory of signatures, we are able to cast this non-linear problem as a high-dimensional linear regression.
  arXiv  Detail & Related papers  (2023-01-27T10:48:28Z)
• 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)
• A Causality-Based Learning Approach for Discovering the Underlying Dynamics of Complex Systems from Partial Observations with Stochastic Parameterization [1.2882319878552302]
  This paper develops a new iterative learning algorithm for complex turbulent systems with partial observations. It alternates between identifying model structures, recovering unobserved variables, and estimating parameters. Numerical experiments show that the new algorithm succeeds in identifying the model structure and providing suitable parameterizations for many complex nonlinear systems.
  arXiv  Detail & Related papers  (2022-08-19T00:35:03Z)
• Causality-Based Multivariate Time Series Anomaly Detection [63.799474860969156]
  We formulate the anomaly detection problem from a causal perspective and view anomalies as instances that do not follow the regular causal mechanism to generate the multivariate data. We then propose a causality-based anomaly detection approach, which first learns the causal structure from data and then infers whether an instance is an anomaly relative to the local causal mechanism. We evaluate our approach with both simulated and public datasets as well as a case study on real-world AIOps applications.
  arXiv  Detail & Related papers  (2022-06-30T06:00:13Z)
• 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)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  empirical optimization is central to modern machine learning, but its role in its success is still unclear. We show that it commonly arises in parameters of discrete multiplicative noise due to variance. A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
  arXiv  Detail & Related papers  (2020-06-11T09:58:01Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

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.