{"ID":2842617,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.08993","arxiv_id":"2511.08993","title":"Fast $k$-means clustering in Riemannian manifolds via Fréchet maps: Applications to large-dimensional SPD matrices","abstract":"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échet map $F^p : \\mathcal{M} \\to \\mathbb{R}^\\ell$ -- defined on a generic metric space $\\mathcal{M}$ -- which embeds the manifold data into a lower-dimensional Euclidean space $\\mathbb{R}^\\ell$ using a set of reference points $\\{r_i\\}_{i=1}^\\ell$, $r_i \\in \\mathcal{M}$. Once embedded, we can efficiently and accurately apply standard Euclidean clustering techniques such as k-means. We rigorously analyze the mathematical properties of $F^p$ in the Euclidean space and the challenging manifold of $n \\times n$ symmetric positive definite matrices $\\mathit{SPD}(n)$. Extensive numerical experiments using synthetic and real $\\mathit{SPD}(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.","short_abstract":"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échet map $F^p : \\mathcal{M} \\to \\mathbb{R}^\\ell$ -- defined on a generic metric s...","url_abs":"https://arxiv.org/abs/2511.08993","url_pdf":"https://arxiv.org/pdf/2511.08993v1","authors":"[\"Ji Shi\",\"Nicolas Charon\",\"Andreas Mang\",\"Demetrio Labate\",\"Robert Azencott\"]","published":"2025-11-12T05:28:31Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.CV\",\"math.DG\"]","methods":"[]","has_code":false}