Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion
Authors: Richard Zhang, Salar Fattahi, Somayeh Sojoudi
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The algorithm is highly efficient in practice: we solve the associated MDMC problems 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. In Section 4, we present computation results on a suite of test cases. Both synthetic and real-life graphs are considered. |
| Researcher Affiliation | Academia | 1Department of Industrial Engineering and Operations Research, University of California, Berkeley, USA. 2Department of Electrical Engineering and Computer Science, University of California, Berkeley, USA. |
| Pseudocode | Yes | Figure 1. MATLAB code for chordal embedding via its internal approximate minimum degree ordering. Given a sparse matrix (C), compute a chordal embedding (Gt) and the number of added edges (m). p = amd(C); % fill-reducing ordering [h,~,~,~,R] = symbfact(C(p,p)); Gt = R+R'; Gt(p,p) = Gt; m = nnz(R)-nnz(tril(C)); |
| Open Source Code | Yes | MATLAB source code: http://alum.mit.edu/www/ ryz. |
| Open Datasets | Yes | The actual graphs (i.e. the sparsity patterns) for Σ 1 are chosen from Suite Sparse Matrix Collection (Davis & Hu, 2011) a publicly available dataset for large-and-sparse matrices collected from real-world applications. |
| Dataset Splits | No | The paper describes how synthetic and real-life graphs are used, and how samples are generated, but it does not specify explicit training, validation, or test dataset splits (e.g., 80/10/10 percentages or specific sample counts for each split). |
| Hardware Specification | Yes | All experiments are performed on a laptop computer with an Intel Core i7 quad-core 2.50 GHz CPU and 16GB RAM. |
| Software Dependencies | Yes | The reported results are based on a serial implementation in MATLAB-R2017b. |
| Experiment Setup | Yes | Our implementation used γ = 0.01 and ρ = 0.5. Both our Newton decrement threshold and QUIC s convergence threshold are 10 7. In all of our simulations, the threshold λ is set so that the number of nonzero elements in the the estimator is roughly the same as the ground truth. |