K-means with learned metrics
Not on the map. Why?
Abstract (arXiv)
We study the Fr'echet k-means of a metric measure space when both the measure and the distance are unknown and have to be estimated. We prove a general result that states that the k-means are continuous with respect to the measured Gromov-Hausdorff topology. In this situation, we also prove a stability result for the Voronoi clusters they determine. We do not assume uniqueness of the set of k-means, but when it is unique, the results are stronger. This framework provides a unified approach to proving consistency for a wide range of metric learning procedures. As concrete applications, we obtain new consistency results for several important estimators that were previously unestablished, even when k=1. These include k-means based on: (i) Isomap and Fermat geodesic distances on manifolds, (ii) difussion distances, (iii) Wasserstein distances computed with respect to learned ground metrics. Finally, we consider applications beyond the statistical inference paradigm like (iv) first passage percolation and (v) discrete approximations of length spaces.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 15 of its 63 references that are in the map. First posted on arXiv 15 Mar 2026.
Builds on
15 of 63 references.
References · 15
- 2018Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operatorcited by 70
- 2020Spectral convergence of diffusion maps: improved error bounds and an alternative normalisationcited by 25
- 2020Balancing Geometry and Density: Path Distances on High-Dimensional Datacited by 16
- 2022Wasserstein K-means for clustering probability distributionscited by 16
- 2023Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithmscited by 12
- 2019Power Weighted Shortest Paths for Clustering Euclidean Datacited by 10
- 2020Intrinsic persistent homology via density-based metric learningcited by 9
- 2022Asymptotic Theory of Geometric and Adaptive k-Means Clusteringcited by 4
- 2019On clustering uncertain and structured data with Wasserstein barycenters and a geodesic criterion for the number of clusterscited by 3
- 2023Choosing the parameter of the Fermat distance: navigating geometry and noisecited by 2
- 2024A kernel-based analysis of Laplacian Eigenmapscited by 2
- 2025Manifold learning in metric spacescited by 2
3 more
- 2024Wasserstein k-Centers Clustering for Distributional Datacited by 1
- 2024On uniqueness of the set of k-meanscited by 1
- 2025Finite sample bounds for barycenter estimation in geodesic spacescited by 1
Built on by
Not cited yet.