Improving geodesic distance estimation based on locally linear assumption

Geodesic distance estimation for data lying on a manifold is an important issue in many applications of nonlinear dimensionality reduction. In this paper, a method aiming at improving the precision of geodesic distance estimation is proposed. The method is constructed on the basic principle, locally linear assumption, underlying the manifold data. It presumes that the locally linear patch, expressed as a convex combination of neighbors of a vertex, approximately resides on the manifold, as well as the local neighborhood edge does. The proposed method essentially extends the search area from local edges, employed by existing methods, to local patches. This naturally leads to a more accurate geodesic distance estimation. An efficient algorithm for the method is constructed, and its computational complexity is also analyzed. Experiment results also show that the proposed method outperforms the existing methods in geodesic distance estimation. © 2008 Elsevier B.V. All rights reserved.