标题： 图Lasso与阈值化：等价性和闭式解 显示英文标题

标题： Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions

摘要： 图拉索（GL）是一种用于学习无向图模型结构的流行方法，它基于一种正则化技术$l_1$。 本文的目的在于比较计算密集型的GL技术与一种基于简单阈值处理样本协方差矩阵的数值廉价启发式方法。 为此，发展了符号一致和逆一致矩阵的两个概念，并且证明如果：(i) 阈值处理后的样本协方差矩阵既是符号一致又是逆一致，以及(ii) 样本协方差矩阵中最大阈值处理条目与最小未处理条目之间的差距不太小，则阈值处理方法与GL方法是等价的。 在此基础上，证明了当阈值处理后的样本协方差矩阵具有无环结构时，GL方法作为一个锥优化问题具有显式的闭式解。 此结果被推广到任意稀疏支持图，找到了一个公式来获得GL的近似解。 此外，还表明随着稀疏图中最小长度循环长度的增加，导出的显式公式的近似误差以指数速度减小。 这些结果在合成数据、功能磁共振成像数据、交通网络的交通流以及大规模随机生成的数据集上进行了演示。 我们展示了所提出的方法可以在标准笔记本电脑上运行MATLAB，在不到30分钟的时间内准确地近似求解大小高达$80,000\times 80,000$（超过32亿个变量）的GL实例，而其他最先进的方法在4小时内无法收敛。 显示英文摘要

摘要： 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.