3
$\begingroup$

all, I'm doing a graphical lasso in order to approximate the inverse of the covariance matrix of a 1200 (p-features) by 100 or so (n observations) data matrix. Basically, I'm inverting a 1200 x 1200 covariance matrix using the glasso function from the glasso package in R. So far it has taken 48 hours and this is just not acceptable. The rho coefficient is set to 0.25, which I think is pretty generous.

Can anyone help me understand how I can speed this up? Is there a better implementation out there? I understand complexity concerns, but I do not have an idea about if this method is just slow because of inefficient code, or if I need to do feature selection before I do the covariance matrix and then the graphical LASSO.

Looking forward to your thoughts!

$\endgroup$
5
  • $\begingroup$ Well, not familiar with glasso. Perhaps some other implementations are fasyer but your matrix is pretty big to calculate an inverse. What is your performance goal? $\endgroup$ Jan 19 '16 at 18:13
  • $\begingroup$ I'd like to get it under 12 hours, ideally. The good news is this is a structural learner, and I'd only need to do it once. However, waiting more than a day is ridiculous! $\endgroup$ Jan 19 '16 at 18:15
  • $\begingroup$ Ok, first I'd check how your data set would look after some dimensionality reduction. Otherwise, if your cov matrix is sparse, we could exploit that. We have, sort to speak, two ways to go. $\endgroup$ Jan 19 '16 at 18:21
  • 1
    $\begingroup$ Complaining about slow inversion of a 1200x1200 matrix by a package written by Friedman, Hastie and Tibshirani? Kids these days, I tell ya... $\endgroup$
    – Cliff AB
    Jan 19 '16 at 19:19
  • $\begingroup$ Haha, funny Cliff AB! $\endgroup$ Jan 19 '16 at 19:34
1
$\begingroup$

There are sure-screening rules that allow one to divide the precision matrix into disconnected blocks, based on thresholding the sample covariance matrix. The R package "huge" implements some of these screening rules (and based on the authors' timings, seems be faster than glasso, anyways). See http://www.jmlr.org/papers/volume13/zhao12a/zhao12a.pdf .

$\endgroup$
1
$\begingroup$

Here's what I've come to. There is a approx parameter glasso that is set to FALSE as a default. Setting it to TRUE enables the Meinhausen-Buhlmann(2006) approximation and VASTLY decreases computation time. Choosing this option and doing feature selection beforehand made my runtime seconds long. These are concessions that are not trivial, but they suit my needs.

$\endgroup$
1
  • $\begingroup$ I feel silly. Good catch! $\endgroup$ Jan 19 '16 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.