We consider a networked linear dynamical system with $p$ agents/nodes. We study the problem of learning the underlying graph of interactions/dependencies from observations of the nodal trajectories over a time-interval $T$. We present a regularized non-casual consistent estimator for this problem and analyze its sample complexity over two regimes: (a) where the interval $T$ consists of $n$ i.i.d. observation windows of length $T/n$ (restart and record), and (b) where $T$ is one continuous observation window (consecutive). Using the theory of $M$-estimators, we show that the estimator recovers the underlying interactions, in either regime, in a time-interval that is logarithmic in the system size $p$. To the best of our knowledge, this is the first work to analyze the sample complexity of learning linear dynamical systems \emph{driven by unobserved not-white wide-sense stationary (WSS) inputs}.
翻译:我们考虑的是带有美元代理商/节点的网络线性动态系统。我们研究从对节点轨迹的观察中学习互动/依赖性的基本图解的问题,在时间与时间间隔期间,用美元来研究。我们为这一问题提出了一个固定的非连续一致的估算器,并分析其在两种制度中的抽样复杂性:(a) 时间间隔为美元/美元(美元/美元)(重新开始和记录),(b) 时间长度为美元/美元/美元(重新开始和记录)的观察窗口,(美元)是一个连续观测窗口(连续观测窗口)。我们利用美元估算器的理论,我们表明,在两种制度中,估计器在时间间隔中都恢复了基本的互动,在系统规模上是逻辑性的,美元。据我们所知,这是对学习线性动态系统的抽样复杂性进行分析的首项工作。