Empirical averages are a basic statistical tool, but on curved spaces their natural analogue—the Fréchet mean—rarely has a closed form. In a new preprint, Ian McPherson and Mauro Maggioni study the harder case where data lie on an unknown compact d-dimensional Riemannian manifold embedded in an ambient metric space. This occurs, for example, when observations are probability distributions compared in Wasserstein space.

Rather than assuming access to the manifold's intrinsic geometry, their algorithm only needs a local sampler on the manifold and the observed metric. It builds a graph from sampled points and iteratively refines approximations to geodesic interpolation. Under mild assumptions, the authors prove an expected objective gap of O(1/T) after T iterations, using at most O~(T^{4d+3}) sampled points.

As a byproduct, the analysis extends metric-equivalence guarantees for ISOMAP from Euclidean to Riemannian ambient spaces, a result that may be independently useful. Numerical experiments show the method can compute intrinsic averages on unknown data manifolds.