Minimax Estimation of Distances on a Surface and Minimax Manifold Learning in the Isometric-to-Convex Setting
This work provides theoretical guarantees for distance estimation and manifold learning on smooth submanifolds, which is significant for researchers and practitioners working with high-dimensional data embedding and geometric analysis.
This paper addresses the problem of estimating intrinsic distances on a smooth submanifold and proposes a minimax optimal approach using surface reconstruction, specifically the tangential Delaunay complex. It then extends this concept to manifold learning, demonstrating that a modified Isomap, which computes distances on a reconstructed surface, achieves minimax optimality for the isometric manifold learning problem.
We start by considering the problem of estimating intrinsic distances on a smooth submanifold. We show that minimax optimality can be obtained via a reconstruction of the surface, and discuss the use of a particular mesh construction -- the tangential Delaunay complex -- for that purpose. We then turn to manifold learning and argue that a variant of Isomap where the distances are instead computed on a reconstructed surface is minimax optimal for the isometric variant of the problem.