A New Approach to Learning Linear Dynamical Systems
- URL: http://arxiv.org/abs/2301.09519v1
- Date: Mon, 23 Jan 2023 16:07:57 GMT
- Title: A New Approach to Learning Linear Dynamical Systems
- Authors: Ainesh Bakshi, Allen Liu, Ankur Moitra and Morris Yau
- Abstract summary: We provide the first time algorithm for learning a linear dynamical system from a length trajectory up to error in the system parameters.
Our algorithm is built on a method of moments estimator to directly estimate parameters from which the dynamics can be extracted.
- Score: 19.47235707806519
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Linear dynamical systems are the foundational statistical model upon which
control theory is built. Both the celebrated Kalman filter and the linear
quadratic regulator require knowledge of the system dynamics to provide
analytic guarantees. Naturally, learning the dynamics of a linear dynamical
system from linear measurements has been intensively studied since Rudolph
Kalman's pioneering work in the 1960's. Towards these ends, we provide the
first polynomial time algorithm for learning a linear dynamical system from a
polynomial length trajectory up to polynomial error in the system parameters
under essentially minimal assumptions: observability, controllability, and
marginal stability. Our algorithm is built on a method of moments estimator to
directly estimate Markov parameters from which the dynamics can be extracted.
Furthermore, we provide statistical lower bounds when our observability and
controllability assumptions are violated.
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) - Data-Driven Control with Inherent Lyapunov Stability [3.695480271934742]
We propose Control with Inherent Lyapunov Stability (CoILS) as a method for jointly learning parametric representations of a nonlinear dynamics model and a stabilizing controller from data.
In addition to the stabilizability of the learned dynamics guaranteed by our novel construction, we show that the learned controller stabilizes the true dynamics under certain assumptions on the fidelity of the learned dynamics.
arXiv Detail & Related papers (2023-03-06T14:21:42Z) - Time varying regression with hidden linear dynamics [74.9914602730208]
We revisit a model for time-varying linear regression that assumes the unknown parameters evolve according to a linear dynamical system.
Counterintuitively, we show that when the underlying dynamics are stable the parameters of this model can be estimated from data by combining just two ordinary least squares estimates.
arXiv Detail & Related papers (2021-12-29T23:37:06Z) - Learning over All Stabilizing Nonlinear Controllers for a
Partially-Observed Linear System [4.3012765978447565]
We propose a parameterization of nonlinear output feedback controllers for linear dynamical systems.
Our approach guarantees the closed-loop stability of partially observable linear dynamical systems without requiring any constraints to be satisfied.
arXiv Detail & Related papers (2021-12-08T10:43:47Z) - 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) - Learning Unstable Dynamics with One Minute of Data: A
Differentiation-based Gaussian Process Approach [47.045588297201434]
We show how to exploit the differentiability of Gaussian processes to create a state-dependent linearized approximation of the true continuous dynamics.
We validate our approach by iteratively learning the system dynamics of an unstable system such as a 9-D segway.
arXiv Detail & Related papers (2021-03-08T05:08:47Z) - Online Stochastic Gradient Descent Learns Linear Dynamical Systems from
A Single Trajectory [1.52292571922932]
We show that if the unknown weight matrices describing the system are in Brunovsky canonical form, we can efficiently estimate the ground truth unknown of the system.
Specifically, by deriving concrete bounds, we show that SGD converges linearly in expectation to any arbitrary small Frobenius norm distance from the ground truth weights.
arXiv Detail & Related papers (2021-02-23T17:48:39Z) - 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) - Adaptive Control and Regret Minimization in Linear Quadratic Gaussian
(LQG) Setting [91.43582419264763]
We propose LqgOpt, a novel reinforcement learning algorithm based on the principle of optimism in the face of uncertainty.
LqgOpt efficiently explores the system dynamics, estimates the model parameters up to their confidence interval, and deploys the controller of the most optimistic model.
arXiv Detail & Related papers (2020-03-12T19:56:38Z)
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.