Averaging data points is a core operation in statistics, but on curved spaces the natural generalization—the Fréchet mean—rarely has a closed form. This paper considers the harder setting where the data lie on an unknown compact submanifold of a Riemannian manifold, and only a local sampling mechanism and an observation metric are available. The authors propose a graph-based iterative algorithm that adaptively samples the manifold and approximates geodesic interpolation without knowing its intrinsic geometry.
The method comes with a theoretical guarantee: under mild assumptions, it achieves an expected objective gap of O(1/T) using at most O~(T^{4d+3}) sampled points, where d is the manifold dimension. This makes the approach suitable for non-Euclidean data such as probability distributions in Wasserstein space.
As a byproduct of the analysis, the authors extend the metric equivalence guarantees of ISOMAP from Euclidean to Riemannian ambient spaces, a result that may be independently useful. Numerical experiments demonstrate that the algorithm computes intrinsic averages effectively on unknown data manifolds.