Fast Multiscale Neighbor Embedding.

Area of Science:

• Data Science
• Machine Learning
• Computational Statistics

Background:

• Dimension reduction (DR) techniques create low-dimensional (LD) representations of high-dimensional (HD) data.
• Neighbor embedding (NE) algorithms like t-SNE excel at DR but face computational challenges with large datasets.
• Existing multiscale NE methods struggle with computational complexity due to dense similarity structures.

Purpose of the Study:

• To develop computationally efficient, randomized accelerations for multiscale neighbor embedding methods.
• To enable the application of multiscale NE techniques to large-scale high-dimensional datasets.
• To improve the preservation of neighborhood structures from HD to LD spaces.

Main Methods:

• Subsampling HD data at different scales to identify relevant neighbor sets using vantage-point trees.
• Employing a Barnes-Hut algorithm for efficient cost function and gradient evaluation.
• Implementing randomized accelerations for multiscale NE schemes.

Main Results:

• The proposed accelerations are orders of magnitude faster than original multiscale methods.
• Statistically significant improvements in preserving HD neighborhoods compared to single-scale methods.
• Achieved high-quality LD embeddings suitable for large datasets.

Conclusions:

• Randomized accelerations make advanced multiscale NE methods computationally feasible for big data.
• The developed approach offers superior neighborhood preservation and efficiency for DR tasks.
• Publicly available code facilitates the adoption of these accelerated multiscale NE techniques.