Low-Rank Riemannian Optimization on Positive Semidefinite Stochastic Matrices with Applications to Graph Clustering
- Creators
- Douik, Ahmed
- Hassibi, Babak
Abstract
This paper develops a Riemannian optimization framework for solving optimization problems on the set of symmetric positive semidefinite stochastic matrices. The paper first reformulates the problem by factorizing the optimization variable as X=YY^T 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 paper 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 state-of-the-art Euclidean and Riemannian approaches for graph clustering applications.
Additional Information
© 2018 by the author(s). The authors would like to thank Ramya Korlakai Vinayak for collecting and providing the real-world data used in this manuscript. The authors also extend their thank to the reviewers for their insightful and valuable comments.Attached Files
Published - douik18a.pdf
Files
Name | Size | Download all |
---|---|---|
md5:602aac2e9d9589f6f057eb6df332b102
|
360.0 kB | Preview Download |
Additional details
- Eprint ID
- 109073
- Resolver ID
- CaltechAUTHORS:20210511-092854252
- Created
-
2021-05-12Created from EPrint's datestamp field
- Updated
-
2021-05-12Created from EPrint's last_modified field