Abstract

This paper develops a Riemannian optimization framework for solving optimization problems on the set of symmetric positive semidefinite stochas tic matrices. The paper first reformulates the pro lem by factorizing the optimization variable as X = YYT and deriving conditions on p, i.e., the number of columns of Y, under which the factorization yields a satisfactory solution. The reparameterization of the problem allows its formulation as an optimization over either an embedded or quotient Riemannian manifold whose geometries are investigated. In particular, the pape explicitly derives the tangent space, Riemannian gradients and retraction operator that allow the design of efficient optimization methods on the proposed manifolds. The numerical results reveal that, when the optimal solution has a known low-rank, the resulting algorithms present a clear complexity advantage when compared with stateof-the-art Euclidean and Riemannian approaches for graph clustering applications.