Learning structured matrices in high dimensions: Low rank estimation and structured graphical models

Thesis (Ph.D.)--University of Washington, 2015The topic of learning matrix structures in the emph{high-dimensional statistical setting} has received a lot of attention in machine learning, statistics and signal processing literature. High dimensional setting refers to problems that have more parameters to estimate than samples or measurements. Examples of problems that fall in this area include matrix factorization, matrix rank minimization, and graphical model estimation. These problems arise in many applications including collaborative filtering, system identification, and learning gene-regulatory networks. The focus of this thesis is on the algorithmic and theoretical aspects of learning matrix structures in the high dimensional setting with emphasis on the two problems of matrix rank minimization and graphical model estimation. We first consider the problem of reconstructing a low-rank matrix given a few linear measurements. This problem is known to be NP-hard. We propose a family of iterative reweighted algorithms that reconstruct the low-rank matrix efficiently and accurately. We also give recovery guarantees for these algorithms under suitable assumptions on the measurement maps. Finally, we also apply our algorithms to the problems of system identification and matrix completion. Our extensive numerical experiments illustrate that our algorithms perform better than state of the art algorithms on both synthetic and real data when the rank of the true underlying matrix is unknown. We next consider the problem of learning structured Gaussian graphical models in the high dimensional setting. This problem has a lot of applications ranging from biological modeling to social networks. While existing literature focuses on learning Gaussian graphical models using a simple sparsity regularizer (e.g. the graphical lasso formulation), applications often present prior knowledge that require more structured regularizers. Examples of networks that occur in applications include scale-free networks (where a few nodes have a high degree), community networks (where the connections occur in small dense communities), etc. We propose the structured graphical lasso formulation, a framework that generalizes graphical lasso to learning graphical models with arbitrary user-specified structures. We continue by considering a special case of the structured graphical lasso that pertains to learning graphical model with a few hub nodes. We propose an ADMM algorithm to solve this formulation. Empirical studies indicate the superiority of hub graphical lasso over graphical lasso and other traditional methods in learning graphs with few hubs. We also give model selection consistency results for recovering graphs with few hubs. When the number of hubs to be learned is O(1), hub graphical lasso requires far fewer samples than graphical lasso to learn the right graphical model. We move on to study the problem of estimating multiple Gaussian graphical models where information is shared between the graphical models. We propose different formulations that capture different ways in which information is shared between the networks. Our empirical results indicate that our approach does better than existing approaches in estimating gene-regulatory networks with shared information. We switch gears by focusing on methods to reduce computational time for our models. We note that the proposed ADMM algorithm for hub graphical lasso and other formulations, though effective, involves a singular value decomposition in each iteration whose computational cost can be prohibitive for large problem sizes. To alleviate the computational bottle neck, we first provide algorithm independent approaches (based on screening rules) to speed up our proposed convex formulations. These screening rules are used to break down the problem into independent sub-problems (where possible), yielding significant speed-ups in computation. Typical algorithms for learning sparse graphical models require a Cholesky computation to check for positive definiteness of the iterates. We propose a block-coordinate descent algorithm with step-size selection rules that avoid expensive Cholesky checks and only rely on matrix vector multiplies in each iteration. Our empirical results show significant speed ups over the SVD based ADMM algorithm