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.