Timezone: »

Low-Rank Riemannian Optimization on Positive Semidefinite Stochastic Matrices with Applications to Graph Clustering
Ahmed Douik · Babak Hassibi

Thu Jul 12 08:40 AM -- 08:50 AM (PDT) @ A9
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 $\mathbf{X}=\mathbf{Y}\mathbf{Y}^T$ and deriving conditions on $p$, i.e., the number of columns of $\mathbf{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.

Author Information

Ahmed Douik (California Institute of technology)

Ahmed Douik (S'13) received the Eng. degree in electronic and communication engineering (with first class honors) from the Ecole Polytechnique de Tunisie, Tunisia, in 2013, the M.S. degree in electrical engineering from King Abdullah University of Science and Technology, Thuwal, Saudi Arabia, in 2015. He is now pursuing his Ph.D. at the California Institute of Technology, Pasadena, CA, USA. His research interests include cloud-radio access networks, network coding, single and multi-hop transmissions, and cooperation communication.

Babak Hassibi (Caltech)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors