Robust Laplacian Eigenmaps Using Global Information

The Laplacian Eigenmap is a popular method for non-linear dimension reduction and data representation. This graph based method uses a Graph Laplacian matrix that closely approximates the Laplace-Beltrami operator which has properties that help to learn the structure of data lying on Riemaniann manifolds. However, the Graph Laplacian used in this method is derived from an intermediate graph that is built using local neighborhood information. In this paper we show that it possible to encapsulate global information represented by a Minimum Spanning Tree on the data set and use it for effective dimension reduction when local information is limited. The ability of MSTs to capture intrinsic dimension and intrinsic entropy of manifolds has been shown in a recent study. Based on that result we show that the use of local neighborhood and global graph can preserve the locality of the manifold. The experimental results validate the simultaneous use of local and global information for non-linear dimension reduction.