A Caltech Library Service

Low-Rank Riemannian Optimization for Graph-Based Clustering Applications

Douik, Ahmed and Hassibi, Babak (2021) Low-Rank Riemannian Optimization for Graph-Based Clustering Applications. IEEE Transactions on Pattern Analysis and Machine Intelligence . ISSN 0162-8828. (In Press)

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


With the abundance of data, machine learning applications engaged increased attention in the last decade. An attractive approach to robustify the statistical analysis is to preprocess the data through clustering. This paper develops a low-complexity Riemannian optimization framework for solving optimization problems on the set of positive semidefinite stochastic matrices. The low-complexity feature of the proposed algorithms stems from the factorization of the optimization variable X = YY^T and deriving conditions on the number of columns of Y under which the factorization yields a satisfactory solution. The paper further investigates the embedded and quotient geometries of the resulting Riemannian manifolds. In particular, the paper explicitly derives the tangent space, Riemannian gradients and Hessians, and a retraction operator allowing the design of efficient first and second-order optimization methods for the graph-based clustering applications of interest. The numerical results reveal that the resulting algorithms present a clear complexity advantage as compared with state-of-the-art Euclidean and Riemannian approaches for graph clustering applications.

Item Type:Article
Related URLs:
URLURL TypeDescription
Douik, Ahmed0000-0001-7791-9443
Additional Information:© 2021 IEEE. A part of this paper [1] appears in proc. of International Conference on Machine Learning (ICML’ 2018), Stockholm, Sweden. The authors would like to express their gratitude to the reviewers for their careful reading, their insightful, and valuable comments which helped to highly improve the quality of the manuscript.
Subject Keywords:Riemannian manifolds, Low-rank factorization, graph-based clustering, convex and non-convex optimization
Record Number:CaltechAUTHORS:20210503-115705141
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108941
Deposited By: George Porter
Deposited On:04 May 2021 14:15
Last Modified:04 May 2021 14:15

Repository Staff Only: item control page