FMM-t-SNE
Accelerating t-SNE withthe fast multipole method
L.F.W. Furer (TU Delft - Electrical Engineering, Mathematics and Computer Science)
K.A. Hildebrandt – Mentor (TU Delft - Computer Graphics and Visualisation)
J.R.C. Campolatarro – Mentor (TU Delft - Computer Graphics and Visualisation)
H.X. Lin – Graduation committee member (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The t-Distributed Stochastic Neighbor Embedding (t-SNE) algorithm is a tool for analyzing high-dimensional data, such as RNA sequencing data from brain cells. However, its applicability to large datasets is limited by the quadratic complexity of its gradient computation, which arises from all-to-all interactions between points. This computation can be interpreted as an N-body problem, enabling the use of approximation methods to accelerate evaluation.This work investigates the fast multipole method (FMM), a hierarchical N-body solver based on multipole expansions, as an acceleration strategy for t-SNE. To further optimize performance, a time-varying theta parameter is introduced to adapt the approximation accuracy during optimization. FMM is integrated into the t-SNE framework and evaluated against existing approaches, including the Barnes-Hut (BH) method and the particle-mesh method (PM). Results show that FMM outperforms other BH-like methods in terms of the error–time trade-off, but does not match the performance of PM. The proposed time-varying theta parameter enables FMM to achieve a lower embedding cost within the same runtime as PM, improving the cost–time trade-off despite not surpassing its error–time efficiency.