SVD-Based Screening for the Graphical Lasso

SVD-Based Screening for the Graphical Lasso

Yasuhiro Fujiwara, Naoki Marumo, Mathieu Blondel, Koh Takeuchi, Hideaki Kim, Tomoharu Iwata, Naonori Ueda

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 1682-1688. https://doi.org/10.24963/ijcai.2017/233

The graphical lasso is the most popular approach to estimating the inverse covariance matrix of high-dimension data. It iteratively estimates each row and column of the matrix in a round-robin style until convergence. However, the graphical lasso is infeasible due to its high computation cost for large size of datasets. This paper proposes Sting, a fast approach to the graphical lasso. In order to reduce the computation cost, it efficiently identifies blocks in the estimated matrix that have nonzero elements before entering the iterations by exploiting the singular value decomposition of data matrix. In addition, it selectively updates elements of the estimated matrix expected to have nonzero values. Theoretically, it guarantees to converge to the same result as the original algorithm of the graphical lasso. Experiments show that our approach is faster than existing approaches.
Keywords:
Machine Learning: Data Mining
Machine Learning: Learning Graphical Models
Machine Learning: Structured Learning
Multidisciplinary Topics and Applications: Multidisciplinary Topics and Applications