Kavraki Lab

Physical and Biological Computing

URL:

Keywords:

Abstract:

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.

• BibTex
• Endnote Tagged
• Endnote XML
• PDF
• Publisher's web site