GVARCLUS Procedure

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: