Distance Preserving Dimension Reduction for Manifold Learning
Hyunsoo Kim, Haesun Park, Hongyuan Zha · 2007
Manifold learning is an effective methodology for extracting nonlinear structures from high-dimensional data with many applications in image analysis, computer vision, text data analysis and bioinformatics. The focus of this paper is on developing algorithms for reducing the computational complexity of manifold learning algorithms, in particular, we consider the case when the number of features is much larger than the number of data points. To handle the large number of features, we propose a preprocessing method, distance preserving dimension reduction (DPDR). It produces t-dimensional representations of the high-dimensional data, where t is the rank of the original dataset. It exactly preserves the Euclidean L2-norm distances as well as cosine similarity measures between data points in the original space. With the original data projected to the t-dimensional space, manifold learning algorithms can be executed to obtain lower dimensional parameterizations with substantial reduction in computational cost. Our experimental results illustrate that DPDR significantly reduces computing time of manifold learning algorithms and produces low-dimensional parameterizations as accurate as those obtained from the original datasets.