An inexact interior point method for L
1-regularized sparse covariance selection |
| |
Authors: | Lu Li Kim-Chuan Toh |
| |
Institution: | 1. Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543, Singapore 2. Singapore-MIT Alliance, 4 Engineering Drive 3, Singapore, 117576, Singapore
|
| |
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 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|