On a Connection between Maximum Variance Unfolding, Shortest Path Problems and IsoMap

We present an equivalent formulation of the Maximum Variance Unfolding (MVU) problem in terms of distance matrices. This yields a novel interpretation of the MVU problem as a regularized version of the shortest path problem on a graph. This interpretation enables us to establish an asymptotic convergence result for the case that the underlying data are drawn from a Riemannian manifold which is isometric to a convex subset of Euclidean space.