E. Plaku and L. E. Kavraki, “Nonlinear Dimensionality Reduction Using Approximate Nearest Neighbors,” in SIAM International Conference on Data Mining (SDM), Minneapolis, Minnesota, 2007, pp. 3711–3716.
Nonlinear dimensionality reduction methods often rely on the nearest-neighbors graph to extract low-dimensional embeddings that reliably capture the underlying structure of high-dimensional data. Research however has shown that computing nearest neighbors of a point from a high-dimensional data set generally requires time proportional to the size of the data set itself, rendering the computation of the nearest-neighbors graph prohibitively expensive. This work significantly reduces the major computational bottleneck of many nonlinear dimensionality reduction methods by efficiently and accurately approximating the nearest-neighbors graph. The approximation relies on a distance-based projection of high-dimensional data onto low-dimensional Euclidean spaces. As indicated by experimental results, the advantage of the proposed approximation is that while it reliably maintains the accuracy of nonlinear dimensionality reduction methods, it significantly reduces the computational time.
Publisher: http://www.siam.org/proceedings/datamining/2007/dm07_preface.php
PDF preprint: http://kavrakilab.org/publications/plaku-kavraki2007nonlinear-dimensionality-reduction.pdf