Optimization Online


Alternating Direction Methods for Sparse Covariance Selection

Xiaoming Yuan(xmyuan***at***hkbu.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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society