On the Sample Complexity of Graphical Model Selection From Non-Stationary Samples

We study conditions that allow accurate graphical model selection from non-stationary data. The observed data is modelled as a vector-valued zero-mean Gaussian random process whose samples are uncorrelated but have different covariance matrices. This model contains as special cases the standard setting of i.i.d. samples as well as the case of samples forming a stationary time series. More generally, our approach applies to any data for which efficient decorrelation transforms, such as the Fourier transform for stationary time series, are available. By analyzing a conceptually simple model selection method, we derive a sufficient condition on the required sample size for accurate graphical model selection based on non-stationary data.