This is the R implementation of Algorithm 1 in Bien, J., and Tibshirani, R.
(2011), "Sparse Estimation of a Covariance Matrix," Biometrika. 98(4).
807--820. The goal is to approximately minimize (over Sigma) the following
non-convex optimization problem:
minimize logdet(Sigma) + trace(S Sigma^-1) + || lambda*Sigma ||_1 subject to
Sigma positive definite.
Here, the L1 norm and matrix multiplication between lambda and Sigma are
elementwise. The empirical covariance matrix must be positive definite for
the optimization problem to have bounded objective (see Section 3.3 of
paper). We suggest adding a small constant to the diagonal of S if it is
not. Since the above problem is not convex, the returned matrix is not
guaranteed to be a global minimum of the problem.
In Section 3.2 of the paper, we mention a simple modification of gradient
descent due to Nesterov. The argument nesterov
controls whether to
use this modification (we suggest that it be used). We also strongly
recommend using backtracking. This allows the algorithm to begin by taking
large steps (the initial size is determined by the argument
step.size
) and then to gradually reduce the size of steps.
At the start of the algorithm, a lower bound (delta
in the paper) on
the eigenvalues of the solution is calculated. As shown in Equation (3) of
the paper, the prox function for our generalized gradient descent amounts to
minimizing (over a matrix X) a problem of the form
minimize (1/2)|| X-A ||_F^2 + || lambda*X ||_1 subject to X >= delta I
This is implemented using an alternating direction method of multipliers
approach given in Appendix 3.