Please use this identifier to cite or link to this item:
Title: An inexact interior point method for L1-regularized sparse covariance selection
Authors: Li, L.
Toh, K.-C. 
Keywords: Inexact interior point method
Inexact search direction
Iterative solver
Log-determinant semidefinite programming
Sparse inverse covariance selection
Issue Date: 2010
Citation: Li, L., Toh, K.-C. (2010). An inexact interior point method for L1-regularized sparse covariance selection. Mathematical Programming Computation 2 (3-4) : 291-315. ScholarBank@NUS Repository.
Abstract: Sparse covariance selection problems can be formulated as logdeterminant (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 solves 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. © Springer and Mathematical Optimization Society 2010.
Source Title: Mathematical Programming Computation
ISSN: 18672949
DOI: 10.1007/s12532-010-0020-6
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.