Learning Large-Scale MTP$_2$ Gaussian Graphical Models via Bridge-Block Decomposition
Xiwen Wang, Jiaxi Ying, Daniel P. Palomar
Abstract
This paper studies the problem of learning the large-scale Gaussian graphical models that are multivariate totally positive of order two ($\text{MTP}_2$). By introducing the concept of bridge, which commonly exists in large-scale sparse graphs, we show that the entire problem can be equivalently optimized through (1) several smaller-scaled sub-problems induced by a \emph{bridge-block decomposition} on the thresholded sample covariance graph and (2) a set of explicit solutions on entries corresponding to \emph{bridges}. From practical aspect, this simple and provable discipline can be applied to break down a large problem into small tractable ones, leading to enormous reduction on the computational complexity and substantial improvements for all existing algorithms. The synthetic and real-world experiments demonstrate that our proposed method presents a significant speed-up compared to the state-of-the-art benchmarks.
BibTeX
@inproceedings{
wang2023learning,
title={Learning Large-Scale {MTP}\$\_2\$ Gaussian Graphical Models via Bridge-Block Decomposition},
author={Xiwen Wang and Jiaxi Ying and Daniel P. Palomar},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=Vfp8sDST4g}
}