Sparse Inverse Covariance Estimation for Chordal Structures
Sparse Inverse Covariance Estimation for Chordal Structures
复制标题
弦结构的稀疏逆协方差估计
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Sojoudi
中科院分区：
文献类型：
--
作者：
S. Fattahi;Richard Y. Zhang;S. Sojoudi
在本文中，我们考虑图形Lasso (GL)，这是一个流行的优化问题，用于学习高维数据集的稀疏表示，众所周知，对于大规模问题来说，它的计算成本很高。最近，我们已经证明了在不同条件下，对于稀疏图，GL的最优解的稀疏模式等同于简单地对样本协方差矩阵进行阈值处理得到的稀疏模式。当阈值样本协方差矩阵具有非循环结构时，我们还推导出了一个最优的闭型解。作为前一结果的主要推广，本文导出了弦结构图的GL的闭形式解。我们表明，如果阈值样本协方差矩阵具有弦结构，则GL和阈值等效条件可以显着简化，并且有望适用于高维问题。然后，我们证明了GL和阈值等价足以将GL简化为最大行列式矩阵补全问题，并在阈值样本协方差矩阵具有弦结构时驱动GL的递归闭形式解。对于多达4.5亿个变量的大规模问题，本文提出的方法可以在不到2分钟的时间内解决GL问题，而目前的方法收敛时间超过2小时。
In this paper, we consider the Graphical Lasso (GL), a popular optimization problem for learning the sparse representations of high-dimensional datasets, which is well-known to be computationally expensive for large-scale problems. Recently, we have shown that the sparsity pattern of the optimal solution of GL is equivalent to the one obtained from simply thresholding the sample covariance matrix, for sparse graphs under different conditions. We have also derived a closed-form solution that is optimal when the thresholded sample covariance matrix has an acyclic structure. As a major generalization of the previous result, in this paper we derive a closed-form solution for the GL for graphs with chordal structures. We show that the GL and thresholding equivalence conditions can significantly be simplified and are expected to hold for high-dimensional problems if the thresholded sample covariance matrix has a chordal structure. We then show that the GL and thresholding equivalence is enough to reduce the GL to a maximum determinant matrix completion problem and drive a recursive closed-form solution for the GL when the thresholded sample covariance matrix has a chordal structure. For large-scale problems with up to 450 million variables, the proposed method can solve the GL problem in less than 2 minutes, while the state-of-the-art methods converge in more than 2 hours.
用于学习大规模稀疏图形模型的线性时间算法
影响因子：
3.9
作者：
Fattahi, Salar;Zhang, Richard;Sojoudi, Somayeh
通讯作者：
Sojoudi, Somayeh