Sample complexity for topology estimation in networks of LTI systems
Vincent Y. F. Tan, Alan S. Willsky · 2011
This paper proposes a consistent and computationally efficient FFT-based algorithm for inferring the network topology where each node in the network is associated to a wide-sense stationary, ergodic, Gaussian process. Each edge of the tree network is characterized by a linear, time-invariant dynamical system and additive white Gaussian noise. The proposed algorithm uses Bartlett's procedure to produce periodogram estimates of cross power spectral densities between processes. Under appropriate assumptions, we prove that the number of vector-valued samples from a single sample path required for consistent estimation is polylogarithmic in the number of nodes in the network. Thus, the sample complexity is low. Our proof uses properties of spectral estimates and analysis for learning tree-structured graphical models.