Alternating Direction Methods for Sparse Covariance Selection
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
Entry Submitted: 09/03/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|