Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding
t-distributed Stochastic Neighborhood Embedding (t-SNE) is a method for dimensionality reduction and visualization that has become widely popular in recent years. Efficient implementations of t-SNE are available, but they scale poorly to datasets with hundreds of thousands to millions of high dimensional data-points. We present Fast Fourier Transform-accelerated Interpolation-based t-SNE (FIt-SNE), which dramatically accelerates the computation of t-SNE. The most time-consuming step of t-SNE is a convolution that we accelerate by interpolating onto an equispaced grid and subsequently using the fast Fourier transform to perform the convolution. We also optimize the computation of input similarities in high dimensions using multi-threaded approximate nearest neighbors. We further present a modification to t-SNE called "late exaggeration," which allows for easier identification of clusters in t-SNE embeddings. Finally, for datasets that cannot be loaded into the memory, we present out-of-core randomized principal component analysis (oocPCA), so that the top principal components of a dataset can be computed without ever fully loading the matrix, hence allowing for t-SNE of large datasets to be computed on resource-limited machines.
Code (8)
Tasks
Dimensionality ReductionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration
Distributed stochastic optimization algorithms can simultaneously process large-scale datasets, significantly accelerating model training. However, their effectiveness is often hindered by the sparsity of distributed net…
Stochastic OptimizationDR-SNE: Density-Regularized Stochastic Neighbor Embedding
Dimensionality-reduction methods such as t-SNE preserve local neighborhood structure but can substantially distort the local distribution of data. We introduce Density-Regularized Stochastic Neighbor Embedding (DR-SNE), …
Dimensionality ReductionAnomaly DetectionT-SNE Is Not Optimized to Reveal Clusters in Data
Cluster visualization is an essential task for nonlinear dimensionality reduction as a data analysis tool. It is often believed that Student t-Distributed Stochastic Neighbor Embedding (t-SNE) can show clusters for well …
ClusteringDimensionality ReductionPerplexity-free Parametric t-SNE
The t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm is a ubiquitously employed dimensionality reduction (DR) method. Its non-parametric nature and impressive efficacy motivated its parametric extension. It …
Dimensionality ReductionQuantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry
We study distributed optimization with stochastic gradients and finite-bit communication modeled by random (unbiased) quantization. We propose q-PDGD, a quantized stochastic primal-dual method, and analyze it under relax…
Distributed Optimization