Graph approximations to geodesics on embedded manifolds
0 Introduction In [1] Tenenbaum, de Silva and Langford consider the problem of non-linear dimensionality reduction: discovering intrinsically low-dimensional structures embedded in high-dimensional data sets. They describe an algorithm, called Isomap, and demonstrate its successful application to several real and synthetic data sets. In this paper, we discuss some of the theoretical claims for Isomap made in [1]. In particular, we give a full proof of the asymptotic convergence theorem referred to in that paper. Isomap deals with finite data sets of points in R n which are assumed to lie on a smooth submanifold M d of low dimension d < n. The algorithm attempts to recover M given only the data points. A crucial stage in the algorithm involves estimating the unknown geodesic distance in M between data points in terms of the graph distance with respect to some graph G constructed on the data points. We show that the two distance metrics approximate each other arbitrarily closely, as the density of data points tends to infinity. Main Theorem A * The authors are listed alphabetically.