Sparse graphical modeling of piecewise-stationary time series

Graphical models are useful for capturing interdependencies of statistical variables in various fields. Estimating parameters describing sparse graphical models of stationary multivariate data is a major task in areas as diverse as biostatistics, econometrics, social networks, and climate data analysis. Even though time series in these applications are often non stationary, revealing interdependencies through sparse graphs has not advanced as rapidly, because estimating such time varying models is challenged by the curse of dimensionality and the associated complexity which is prohibitive. The goal of this paper is to introduce novel algorithms for joint segmentation and estimation of sparse, piecewise stationary, graphical models. The crux of the proposed approach is application of dynamic programming in conjunction with cost functions regularized with terms promoting the right form of sparsity in the right application domain. As a result, complexity of the novel schemes scales gracefully with the problem dimension.