Low-Rank Optimization on the Cone of Positive Semidefinite Matrices

By Michel Journée, Francis R. Bach, Pierre-Antoine Absil, Rodolphe Sepulchre. SIAM Journal on Optimization, 2008

301 citations recorded by the source corpus.

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=YY^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=YY^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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/6b71b8fb5e97dbe599b829e2b0cb76c1036a4952

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

A Riemannian geometry with complete geodesics for the set of positive semidefinite matrices of fixed rank (2013, background): “In Journée et al. (2010), Meyer et al. (2010), Bonnabel et al. (2010), Sepulchre et al. (2010), the authors equip this quotient manifold with the Euclidean metric.”
Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, background): “…sufﬁcient over-parameterization (as is the case with our settings), loss landscape of linear models are well behaved and all local minima are global minima making the problem tractable Burer and Monteiro [2003], Journée et al. [2010], Kawaguchi [2016], Nguyen and Hein [2017], Lee et al. [2016].”
Low-rank Solutions of Linear Matrix Equations via Procrustes Flow (2015, background): “We should note, however, that the authors study general low-rank matrices rather than PSD ones (2)See [JBAS10] for related schemes using manifold optimization.”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “[45] presents a second-order method for (1), based on manifold optimization over the set of all equivalence class O .”
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport (2018, background): “Our objective, in the space of measures, has many local minima, but we build gradient ﬂows that avoids them, relying mainly on the homogeneity properties of J m (see [16, 20] for other uses of homogeneity in non-convex optimization).”
Understanding symmetries in deep networks (2015, background): “On the other hand, optimization over a manifold with symmetries or invariances has been a topic of much research and provides guidance to other simpler metric constructions [8, 9, 10, 11, 12, 13, 14].”
Stochastic Gradient Descent on Riemannian Manifolds (2011, background): “For more details on this manifold see [17].”
Global Optimality of Local Search for Low Rank Matrix Recovery (2016, background): “It was also shown that (under mild conditions) any rank deficient local minima is a global minima [4, 16], providing a post-hoc verifiable sufficient condition for global optimality.”
Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares (2014, background): “Similarly, following the above steps for the B -update we have: Adding (81) and (82) we get (37) concluding the proof of the lemma.”
Discriminative clustering for image co-segmentation (2010, methodology): “To gain another order of magnitude, we adopt the framework for optimization through low-rank matrices proposed in [ 13 ].”
Implicit Regularization in Matrix Factorization (2017, background): “This is not surprising since with large enough d this non-convex problem has no spurious local minima [4, 9] and gradient descent converges almost surely to a global optima [12]; there has also been recent work establishing conditions for global convergence for low d [3, 7].”
Generalized Low Rank Models (2014, background): “However, a theoretical analysis of optimality conditions for rank-constrained semidefinite programs [20] has led to a few algorithms for semidefinite programming based on matrix factorization [19, 1, 70] which guarantee global optimality and converge quickly if the global solution to the problem is ”
The Fixed Points of Off-Policy TD (2011, background): “Although this is now a non-convex problem, local optimization of this objective is still guaranteed to give a global solution to the original semidefinite problem, provided we choose the rank of Y to be sufficient to represent the optimal solution [5].”
Building Deep Networks on Grassmann Manifolds (2016, background): “For more details about the geometry of PSD manifolds and its retraction operation, readers are referred to [7, 38, 46, 31, 30, 2].”
Manopt, a matlab toolbox for optimization on manifolds (2013, background): “Journ´ee et al. (2010) show how optimizing over the ﬁxed-rank spectrahedron can lead to eﬃcient algorithms for sparse PCA.”