Riemannian Fuzzy K-Means on Product Manifolds

**In this paper, we address an open problem: how to perform fast clustering on product manifolds.** With the increasing interest in non-Euclidean data representations, clustering such data has become an important problem. However, a naive extension of the classic K-Means algorithm to product manifolds requires $\mathcal{O}(\nu \omega)$ time, where $\omega$ is the number of alternating iterations and $\nu $ is the time complexity of each Riemannian optimization. Due to the need for numerous Riemannian optimizations, the naive Riemannian K-Means (NRK) is not suitable for large-scale data. To this end, we propose the Riemannian Fuzzy K-Means (RFK) algorithm for product manifolds, which reduces the time complexity to $\mathcal{O}(\nu )$. Importantly, RFK is not a straightforward extension of K-Means or Fuzzy K-Means to manifolds, it leverages the fuzzy relaxation to eliminate alternating updates and achieve a true single-loop optimization. Furthermore, we introduce Radan to accelerate the optimization of RFK. We conduct extensive experiments. RFK and Radan outperform across nearly all metrics in almost every dataset, reaching an impressive level of performance. **RFK and Radan have been integrated into several non-Euclidean machine learning libraries. (See Appendix F)**