CUED Publications database

Low-rank optimization on the cone of positive semidefinite matrices

Journée, M and Bach, F and Absil, P-A and Sepulchre, R (2010) Low-rank optimization on the cone of positive semidefinite matrices. SIAM Journal on Optimization, 20. pp. 2327-2351. ISSN 1052-6234

Full text not available from this repository.

Abstract

We propose an algorithm for solving optimization problems defined on a subset of the cone of symmetric positive semidefinite matrices. This algorithm relies on the factorization X = Y Y T , where the number of columns of Y fixes an upper bound on the rank of the positive semidefinite matrix X. It is thus very effective for solving problems that have a low-rank solution. The factorization X = Y Y T leads to a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second-order optimization method with guaranteed quadratic convergence. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. In contrast to existing methods, the proposed algorithm converges monotonically to the sought solution. Its numerical efficiency is evaluated on two applications: the maximal cut of a graph and the problem of sparse principal component analysis. © 2010 Society for Industrial and Applied Mathematics.

Item Type: Article
Uncontrolled Keywords: Cone of symmetric positive definite matrices Large-scale algorithms Low-rank constraints Maximum-cut algorithms Riemannian quotient manifold Sparse principal component analysis
Subjects: UNSPECIFIED
Divisions: Div F > Control
Depositing User: Cron Job
Date Deposited: 07 Mar 2014 11:25
Last Modified: 22 Dec 2014 01:17
DOI: 10.1137/080731359