Sparse Gaussian graphical model estimation via alternating minimization

• 成果类型: Article
• 署名作者: Dalal, Onkar; Rajaratnam, Bala
• 署名单位: Stanford University; University of California System; University of California Davis
• 刊物名称: BIOMETRIKA
• ISSN/ISSBN: 0006-3444
• DOI: 10.1093/biomet/asx003
• 发表日期: 2017
• 页码: 379395
• 关键词: covariance-selection; 1st-order methods; algorithm; matrices; Lasso

摘要

Several methods have recently been proposed for estimating sparse Gaussian graphical models using l(1)-regularization on the inverse covariance or precision matrix. Despite recent advances, contemporary applications require even faster methods to handle ill-conditioned high-dimensional datasets. In this paper, we propose a new method for solving the sparse inverse covariance estimation problem using the alternating minimization algorithm, which effectively works as a proximal gradient algorithm on the dual problem. Our approach has several advantages: it is faster than state-of-the-art algorithms by many orders of magnitude; its global linear convergence has been rigorously demonstrated, underscoring its good theoretical properties; it facilitates additional constraints on pairwise or marginal relationships between feature pairs based on domain-specific knowledge; and it is better at handling extremely ill-conditioned problems. Our algorithm is shown to be more accurate and faster on simulated and real datasets.