Learning Sparse Dynamical Systems from a Single Sample Trajectory
Salar Fattahi, Nikolai Matni, Somayeh Sojoudi Salar Fattahi is with the Department of Industrial Engineering and Operations Research, University of California, Berkeley. Nikolai Matni is with the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley. Somayeh Sojoudi is with the Departments of Electrical Engineering and Computer Sciences and Mechanical Engineering as well as the Tsinghua-Berkeley Shenzhen Institute, University of California, Berkeley. This work was supported by the ONR Award N00014-18-1-2526, NSF Award 1808859 and AFSOR Award FA9550-19-1-0055.
Abstract
This paper addresses the problem of identifying sparse linear time-invariant (LTI) systems from a single sample trajectory generated by the system dynamics. We introduce a Lasso-like estimator for the parameters of the system, taking into account their sparse nature. Assuming that the system is stable, or that it is equipped with an initial stabilizing controller, we provide sharp finite-time guarantees on the accurate recovery of both the sparsity structure and the parameter values of the system. In particular, we show that the proposed estimator can correctly identify the sparsity pattern of the system matrices with high probability, provided that the length of the sample trajectory exceeds a threshold. Furthermore, we show that this threshold scales polynomially in the number of nonzero elements in the system matrices, but logarithmically in the system dimensions — this improves on existing sample complexity bounds for the sparse system identification problem. We further extend these results to obtain sharp bounds on the $\ell_{\infty}$ -norm of the estimation error and show how different properties of the system—such as its stability level and mutual incoherency—affect this bou
中文速览
从单段轨迹数据中识别大规模稀疏线性动力系统（sparse LTI system identification）的参数，是电网、交通网络等信息物理系统建模的核心难题，而现有方法要么需要多次重置系统以获取独立轨迹，要么无法给出精确的样本复杂度保证。本文提出一种类Lasso（Lasso-like）估计器，直接从单条系统轨迹出发估计稀疏系统矩阵的支撑结构和参数值，并通过精细分析设计矩阵与噪声之间的相关性，严格证明了该估计器的一致性。理论结果表明，所需轨迹长度仅需随系统矩阵非零元素个数呈多项式增长、随系统维度呈对数增长，显著优于已有的样本复杂度界；同时给出了估计误差ℓ∞范数的精确上界，并揭示了系统稳定性水平和互不相干性（mutual incoherency）对误差的影响。这一结论为将数据驱动模型安全地嵌入大规模分布式控制回路提供了理论基础，在电力系统案例研究中也得到了充分验证。
原文 arXiv:1904.09396;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1904.09396v1