Exact Hybrid Covariance Thresholding for Joint Graphical Lasso
This work addresses the computational bottleneck in estimating graphical models for multi-class datasets, offering an incremental improvement over existing thresholding methods.
The paper tackles the problem of estimating multiple related Gaussian graphical models from multi-class data by proposing a hybrid covariance thresholding algorithm that identifies zero entries in precision matrices and splits the joint graphical lasso into smaller subproblems, leading to faster solutions as demonstrated in experiments on simulated and real gene expression data.
This paper considers the problem of estimating multiple related Gaussian graphical models from a $p$-dimensional dataset consisting of different classes. Our work is based upon the formulation of this problem as group graphical lasso. This paper proposes a novel hybrid covariance thresholding algorithm that can effectively identify zero entries in the precision matrices and split a large joint graphical lasso problem into small subproblems. Our hybrid covariance thresholding method is superior to existing uniform thresholding methods in that our method can split the precision matrix of each individual class using different partition schemes and thus split group graphical lasso into much smaller subproblems, each of which can be solved very fast. In addition, this paper establishes necessary and sufficient conditions for our hybrid covariance thresholding algorithm. The superior performance of our thresholding method is thoroughly analyzed and illustrated by a few experiments on simulated data and real gene expression data.