A coordinate descent algorithm for sparse positive definite matrix estimation

This paper proposes a coordinate descent (CD) algorithm that can be used for estimating sparse positive definite matrices. Positive definite matrix estimation is frequently encountered in multivariate statistics, such as estimation of the precision and covariance matrices. The proposed CD algorithm proceeds in a forward stagewise fashion, and iteratively updates the current estimated matrix at either one diagonal entry or two symmetric off-diagonal entries. To assure the positive definiteness of the estimated matrices, the updating step size needs to be appropriately determined based on a simple sufficient and necessary condition. Furthermore, as each iteration updates only one or two coordinates, the sparsity in the estimated matrix can be achieved by early stopping the iteration. Extensive numerical experiments are conducted to demonstrate the effectiveness of the CD algorithm for estimation of the precision and covariance matrices. The CD algorithm is further extended to graph clustering and delivers superior performance as well. © 2013 Wiley Periodicals, Inc., A Wiley Company.