The GVARCLUS Procedure
Graphical Lasso
PROC GVARCLUS uses the graphical lasso (Friedman, Hastie, and Tibshirani 2008) to estimate the inverse covariance matrix. Assume that the observations have a multivariate Gaussian distribution with mean 
and covariance 
. Zeros in the inverse covariance matrix, also called the precision matrix, correspond to conditional independencies among the variables, given other variables. The precision matrix is estimated by solving a maximum likelihood problem with an added 
-norm penalty to increase the sparsity of the precision matrix.
Suppose you have n multivariate normal observations of dimension p, 
. Let 
, and let S be the empirical covariance matrix. The problem is to maximize the following penalized log likelihood over nonnegative definite matrices 
:
Here 
denotes the determinant and 
is the 
norm, the sum of the absolute values of the elements of 
. The scalar parameter 
controls the size of the penalty. The penalty term is a proxy for the number of nonzero elements in .
Let W be the estimate of . Banerjee, El Ghaoui, and d’Aspremont (2008) show that the preceding problem is convex and can be solved by optimizing over each row and the corresponding column of W in a block coordinate descending fashion. They further show that the problem is equivalent to the following dual problem:
where 
and W is partitioned as follows:
Permute the rows and columns so that the one to be updated is always the last. Solve the dual problem, and then update the estimate of W after each stage.
The graphical lasso algorithm solves the dual problem as follows:
-
Start with
, where S is partitioned as follows: 
The diagonal of W remains unchanged in the following steps.
For each
, solve the lasso problem by coordinate descent (Friedman, Hastie, and Tibshirani 2008), which takes as input the inner products 
and 
. This produces a 
vector solution 
. Fill in the corresponding row and column of W using 
. Continue until convergence.