FItSNE

FIt-SNE, short for Fast Interpolation-based t-Distributed Stochastic Neighbor Embedding, is an algorithm for producing low-dimensional embeddings of high-dimensional data. It is a fast variant of t-SNE designed to scale to very large datasets, and is commonly used in domains such as single-cell transcriptomics, image features, and other high-dimensional data analyses.

The method preserves the core idea of t-SNE: points that are nearby in the original space should be close in the embedding, while distant points should be modeled as far apart. FIt-SNE accelerates the computations by replacing exact pairwise kernel evaluations with two interpolation-based approximations. The attractive term, which connects nearby points, is computed using a neighborhood graph and spline-based interpolation. The repulsive term, which involves all points, is evaluated via a fast convolution on a grid using Fourier transforms. This combination reduces the computational complexity and enables near O(N log N) time per iteration for large N.

Implementation details vary, but typical configurations use 2D or 3D embeddings, a perplexity parameter to control neighborhood size, and standard t-SNE features such as early exaggeration and momentum. Some implementations support CPU execution with optional GPU acceleration. The approach emphasizes accuracy of the interpolation grid and spline order to balance speed and embedding quality.

Impact and usage: FIt-SNE has become popular in bioinformatics and beyond for embedding hundreds of thousands to millions of points more efficiently than vanilla t-SNE or Barnes-Hut t-SNE. It is integrated into several data analysis pipelines and libraries, including workflows for single-cell RNA-sequencing data.

Limitations: Like other t-SNE variants, results can be sensitive to parameter choices and do not convey a straightforward probabilistic mapping. The method remains computationally intensive for extremely large datasets and may require substantial memory. It is often used alongside alternative methods such as UMAP for broader global structure comparison.