On the Sample Complexity of Graphical Model Selection for Non-Stationary Processes

We formulate and analyze a graphical model selection method for inferring the conditional independence graph of a high-dimensional non-stationary Gaussian random process (time series) from a finite-length observation. The observed process samples are assumed uncorrelated over time but having different covariance matrices. We characterize the sample complexity of graphical model selection for such processes by analyzing a particular selection method, which is based on sparse neighborhood regression. Our results indicate, similar to the case of i.i.d. samples, accurate GMS is possible even in the high- dimensional regime if the underlying conditional independence graph is sufficiently sparse.