We consider the problem of fitting a Gaussian autoregressive model to a time series, subject to conditional independence constraints. This is an extension of the classical covariance selection problem to time series. The conditional independence constraints impose a sparsity pattern on the inverse of the spectral density matrix, and result in nonconvex quadratic equality constraints in the maximum likelihood formulation of the model estimation problem. We present a semidefinite relaxation, and prove that the relaxation is exact when the sample covariance matrix is block-Toeplitz. We also give experimental results suggesting that the relaxation is often exact when the sample covariance matrix is not block-Toeplitz. In combination with model selection criteria the estimation method can be used for topology selection. Experiments with randomly generated and several real data sets are also included.

Introduction

Graphical models give a graph representation of relations between random variables. The simplest example is a Gaussian graphical model, in which an undirected graph with n nodes is used to describe conditional independence relations between the components of an n-dimensional random variable x ~ N(0, ∑). The absence of an edge between two nodes of the graph indicates that the corresponding components of x are independent, conditional on the other components. Other common examples of graphical models include contingency tables, which describe conditional independence relations in multinomial distributions, and Bayesian networks, which use directed acyclic graphs to represent causal or temporal relations.