Alternating Direction Methods for Sparse Covariance Selection

Xiaoming Yuan(xmyuanhkbu.edu.hk)

Abstract: The mathematical model of the widely-used sparse covariance selection problem (SCSP) is an NP-hard combinatorial problem, whereas it can be well approximately by a convex relaxation problem whose maximum likelihood estimation is penalized by the $L_1$ norm. This convex relaxation problem, however, is still numerically challenging, especially for large-scale cases. Recently, some efficient first-order methods inspired by Nesterov's work have been proposed to solve the convex relaxation problem of SCSP. This paper is to apply the well-known alternating direction method (ADM), which is also a first-order method, to solve the convex relaxation of SCSP. Due to the full exploitation to the separable structure of a simple reformulation of the convex relaxation problem, the ADM approach is very efficient for solving large-scale SCSP. Our preliminary numerical results show that the ADM approach substantially outperforms existing first-order methods for SCSP.

Keywords: Alternating direction method, Sparse covariance selection, First-order methods, Large-scale, Separable structure.

Category 1: Convex and Nonsmooth Optimization

Citation:

Download: [PDF]

Entry Submitted: 09/03/2009
Entry Accepted: 09/04/2009
Entry Last Modified: 09/03/2009

Modify/Update this entry