.png){kind=icon}
返回
Linear-Time Algorithm for Learning Large-Scale Sparse Graphical Models
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2018.2890583.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider the graphical lasso, 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. A recent line of results has shown-under mild assumptions-that the sparsity pattern of the graphical lasso estimator can be retrieved by soft-thresholding the sample covariance matrix. Based on this result, a closed-form solution has been obtained that is optimal when the thresholded sample covariance matrix has an acyclic structure. In this paper, we prove an extension of this result to generalized graphical lasso (GGL), where additional sparsity constraints are imposed based on prior knowledge. Furthermore, we describe a recursive closed-form solution for the problem when the thresholded sample covariance matrix is chordal. By building upon this result, we describe a novel Newton-Conjugate Gradient algorithm that can efficiently solve the GGL with general structures. Assuming that the thresholded sample covariance matrix is sparse with a sparse Cholesky factorization, we prove that the algorithm converges to an epsilon-accurate solution in O(n log(1/epsilon)) time and O(n) memory. The algorithm is highly efficient in practice: we solve instances with as many as 200 000 variables to 7-9 digits of accuracy in less than an hour on a standard laptop computer running MATLAB.
Keyword:
Optimization
graphical models
numerical algorithms
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.6
论文数:
9.8W
被引数:
29.4W
机构
引用论文
.png){kind=icon}
分享收藏Compression and Air Storage Systems for Small Size CAES Plants: Design and Off-design Analysis小型CAES工厂的压缩和空气存储系统: 设计和非设计分析OAAI
OAAI分享收藏Enhancement of permeability estimation by high order polynomial regression for capillary pressure curve correlation with water saturation通过高阶多项式回归提升毛管压力曲线与含水饱和度的相关性，从而改进渗透率估算
OAAI
OAAI分享收藏分享收藏
查看更多内容