FIt-SNE swMATH ID: 34901 Software Authors: George C. Linderman, Manas Rachh, Jeremy G. Hoskins, Stefan Steinerberger, Yuval Kluger Description: Fast Fourier Transform-accelerated Interpolation-based t-SNE (FIt-SNE). t-Stochastic Neighborhood Embedding (t-SNE) is a highly successful method for dimensionality reduction and visualization of high dimensional datasets. A popular implementation of t-SNE uses the Barnes-Hut algorithm to approximate the gradient at each iteration of gradient descent. We accelerated this implementation as follows: Computation of the N-body Simulation: Instead of approximating the N-body simulation using Barnes-Hut, we interpolate onto an equispaced grid and use FFT to perform the convolution, dramatically reducing the time to compute the gradient at each iteration of gradient descent. See the this post for some intuition on how it works. Computation of Input Similarities: Instead of computing nearest neighbors using vantage-point trees, we approximate nearest neighbors using the Annoy library. The neighbor lookups are multithreaded to take advantage of machines with multiple cores. Using ”near” neighbors as opposed to strictly ”nearest” neighbors is faster, but also has a smoothing effect, which can be useful for embedding some datasets (see Linderman et al. (2017)). If subtle detail is required (e.g. in identifying small clusters), then use vantage-point trees (which is also multithreaded in this implementation). Homepage: https://arxiv.org/abs/1712.09005 Source Code: https://github.com/KlugerLab/FIt-SNE Related Software: LargeVis; Scikit; UMAP; Multicore-tsne; COIL-100; Numba; UCI-ml; MNIST; oocPCA; FixMatch; DeepView; ReMixMatch; openTSNE; TriMap; t-SNE; largeVis; word2vec; darch Cited in: 1 Document Cited by 3 Authors 1 Gentner, Timothy Q. 1 McInnes, Leland 1 Sainburg, Tim Cited in 1 Serial 1 Neural Computation Cited in 1 Field 1 Computer science (68-XX) Citations by Year