An inexact interior point method for L1-regularized sparse covariance selection
Lu Li (lilunus.edu.sg)
Abstract: Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal-dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal-dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solve the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.
Keywords: log-determinant semidefinite programming, sparse inverse covariance selection, infeasible interior point method, inexact search direction, symmetric quasi-minimum residual iteration
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Category 2: Convex and Nonsmooth Optimization (Convex Optimization )
Category 3: Applications -- Science and Engineering (Statistics )
Citation: National University of Singapore, February, 2010.
Entry Submitted: 02/20/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|