Graphical Lasso (GL) is a popular method for learning the structure of an
undirected graphical model, which is based on an $l_1$ regularization
technique. The objective of this paper is to compare the computationally-heavy
GL technique with a numerically-cheap heuristic method that is based on simply
thresholding the sample covariance matrix. To this end, two notions of
sign-consistent and inverse-consistent matrices are developed, and then it is
shown that the thresholding and GL methods are equivalent if: (i) the
thresholded sample covariance matrix is both sign-consistent and
inverse-consistent, and (ii) the gap between the largest thresholded and the
smallest un-thresholded entries of the sample covariance matrix is not too
small. By building upon this result, it is proved that the GL method---as a
conic optimization problem---has an explicit closed-form solution if the
thresholded sample covariance matrix has an acyclic structure. This result is
then generalized to arbitrary sparse support graphs, where a formula is found
to obtain an approximate solution of GL. Furthermore, it is shown that the
approximation error of the derived explicit formula decreases exponentially
fast with respect to the length of the minimum-length cycle of the sparsity
graph. The developed results are demonstrated on synthetic data, functional MRI
data, traffic flows for transportation networks, and massive randomly generated
data sets. We show that the proposed method can obtain an accurate
approximation of the GL for instances with the sizes as large as $80,000\times
80,000$ (more than 3.2 billion variables) in less than 30 minutes on a standard
laptop computer running MATLAB, while other state-of-the-art methods do not
converge within 4 hours.

本文比较了 Graphical Lasso 技术与数值便宜的启发式方法，在构建两个类型的矩阵的基础上，当阈值样本协方差矩阵是符号一致、反转一致的同时，且最大阈值和最小阈值之间的差距不是太小的情况下， 阈值和 GL 技术等效，并且建立在此基础上，通过解决一些优化问题，在类别支持图和其他数据集上获得了准确的结果。