Graphical Models of Time Series: Parameter Estimation and Topology Selection

This thesis is concerned with estimation problems in graphical models of time series. The graph topology of a graphical model characterizes conditional independence relations between the variables, so estimation generally involves two problems: topology selection and parameter estimation for a given topology. We first 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 via duality 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. The estimation method can be used for small topology selection problems by enumerating all topologies, solving the estimation problem for each topology and ranking them via model selection criteria such as the Akaike or Bayes information criteria. As a second contribution, we propose an efficient method for learning the topology of graphical models of autoregressive Gaussian time series. The method is based on an l1-type nonsmooth regularization of the conditional maximum likelihood estimation problem used to promote sparsity in the inverse of the estimated spectral density matrix. We describe a heuristic approach for choosing the regularization parameter which controls the sparsity of the esimated inverse spectrum. The estimation accuracy of the topology and AR model is illustrated by numerical examples and experiments with real data sets. Finally, we describe a large-scale algorithm that solves a reformulation of the duals of the above two problems via the gradient projection method. Numerical results show that the method is capable of solving problems of dimensions of several hundred within a reasonable amount of time.