Graphical Models of Time Series: Parameter Estimation and Topology Selection

Jitkomut Songsiri
Advisor: Lieven Vandenberghe

Tuesday, June 1, 2010 at 10:30am
Engr. IV Maxwell Room 57-124

Abstract:
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. 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 $\ell_1$type nonsmooth regularization of the conditional maximum likelihood estimation problem used to promote sparsity in the inverse of the estimated spectral density matrix. 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.

Biography:
Jitkomut Songsiri is currently a PhD candidate at UCLA, Electrical Engineering. She received Bachelor and Master degrees in Electrical Engineering from Chulalongkorn University, Thailand, in 1999 and 2002 respectively. During 20032004, she was a research assistant at Control System laboratory, Chulalongkorn University. In 2004 she was a recipient of the Royal Thai government scholarship and then joined ULCA in 2005. Her main research interest includes convex optimization problems in machine learning, statistical learning, and graphical models. More information can be found at www.ee.ucla.edu/~jitkomut.