A Riemannian Approach for Graph-Based Clustering by Doubly Stochastic Matrices

Convex optimization is a well-established area with applications in almost all fields. However, these convex methods can be rather slow and computationally intensive for high dimensional problems. For a particular class of problems, this paper considers a different approach, namely Riemannian optimization. The main idea is to view the constrained optimization problem as an unconstrained one over a restricted search space (the manifold). Riemannian optimization explicitly exploits the geometry of the problem and often reduces its dimension, thereby potentially allowing significant speedup as compared to conventional approaches. The paper introduces the doubly stochastic, the symmetric, and the definite multinomial manifolds which generalize the simplex. The method is applied to a convex and a non-convex graph-based clustering problem. Theoretical analysis and simulation results demonstrate the efficiency of the proposed method over the state of the art as it outperforms conventional generic and specialized solvers, especially in high dimensions.