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

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.