Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations

Abstract

We study the estimation of the latent variable Gaussian graphical model (LVGGM), where the precision matrix is the superposition of a sparse matrix and a low-rank matrix. In order to speed up the estimation of the sparse plus low-rank components, we propose a sparsity constrained maximum likelihood estimator based on matrix factorization, and an efficient alternating gradient descent algorithm with hard thresholding to solve it. Our algorithm is orders of magnitude faster than the convex relaxation based methods for LVGGM. In addition, we prove that our algorithm is guaranteed to linearly converge to the unknown sparse and low-rank components up to the optimal statistical precision. Experiments on both synthetic and genomic data demonstrate the superiority of our algorithm over the state-of-the-art algorithms and corroborate our theory.

29 pages, 5 figures, 3 tables

References in corpus (7)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Latent variable graphical model selection via convex optimization
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Fast Algorithms for Robust PCA via Gradient Descent
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Learning Latent Variable Gaussian Graphical Models

Cited by in corpus (5)

• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Learning the effect of latent variables in Gaussian Graphical models with unobserved variables
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• Semiblind subgraph reconstruction in Gaussian graphical models