Quadratic sparse Gaussian graphical model estimation method for massive variables
- Publisher:
- IJCAI-INT JOINT CONF ARTIF INTELL
- Publication Type:
- Conference Proceeding
- Citation:
- IJCAI International Joint Conference on Artificial Intelligence, 2020, 2021-January, pp. 2964-2972
- Issue Date:
- 2020-01-01
Closed Access
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
We consider the problem of estimating a sparse Gaussian Graphical Model with a special graph topological structure and more than a million variables. Most previous scalable estimators still contain expensive calculation steps (e.g., matrix inversion or Hessian matrix calculation) and become infeasible in high-dimensional scenarios, where p (number of variables) is larger than n (number of samples). To overcome this challenge, we propose a novel method, called Fast and Scalable Inverse Covariance Estimator by Thresholding (FST). FST first obtains a graph structure by applying a generalized threshold to the sample covariance matrix. Then, it solves multiple block-wise subproblems via element-wise thresholding. By using matrix thresholding instead of matrix inversion as the computational bottleneck, FST reduces its computational complexity to a much lower order of magnitude (O(p2)). We show that FST obtains the same sharp convergence rate O(p(log max{p, n}/n) as other state-of-the-art methods. We validate the method empirically, on multiple simulated datasets and one real-world dataset, and show that FST is two times faster than the four baselines while achieving a lower error rate under both Frobenius-norm and max-norm.
Please use this identifier to cite or link to this item: