Accelerating t-SNE using Tree-Based Algorithms

Title: Accelerating t-SNE using Tree-Based Algorithms
Authors: Laurens van der Maaten
Published: 2014-01-01
Link: https://jmlr.org/papers/v15/vandermaaten14a.html

Abstract

The paper investigates the acceleration of t-SNE–an embedding technique that is commonly used for the visualization of high-dimensional data in scatter plots–using two tree-based algorithms. In particular, the paper develops variants of the Barnes-Hut algorithm and of the dual-tree algorithm that approximate the gradient used for learning t-SNE embeddings in $\mathcal{O}(NlogN)$. Our experiments show that the resulting algorithms substantially accelerate t-SNE, and that they make it possible to learn embeddings of data sets with millions of objects. Somewhat counterintuitively, the Barnes-Hut variant of t-SNE appears to outperform the dual-tree variant.

---