# Fast k-means clustering in Riemannian manifolds via Fr'echet maps: Applications to large-dimensional SPD matrices

arXiv: https://arxiv.org/abs/2511.08993 · HTML: https://mlsanity.com/paper/2511.08993/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2025.

## Abstract (arXiv)

We introduce a novel, efficient framework for clustering data on high-dimensional, non-Euclidean manifolds that overcomes the computational challenges associated with standard intrinsic methods. The key innovation is the use of the p-Fr'echet map Fp : M → ℝℓ -- defined on a generic metric space M -- which embeds the manifold data into a lower-dimensional Euclidean space ℝℓ using a set of reference points rii=1ℓ, ri ∈ M. Once embedded, we can efficiently and accurately apply standard Euclidean clustering techniques such as k-means. We rigorously analyze the mathematical properties of Fp in the Euclidean space and the challenging manifold of n × n symmetric positive definite matrices mathitSPD(n). Extensive numerical experiments using synthetic and real mathitSPD(n) data demonstrate significant performance gains: our method reduces runtime by up to two orders of magnitude compared to intrinsic manifold-based approaches, all while maintaining high clustering accuracy, including scenarios where existing alternative methods struggle or fail.