Dimension Reduction Taxonomy - 4. Non-Linear Manifold Learning: t-SNE and UMAP

4. Non-Linear Manifold Learning: t-SNE and UMAP

Linear methods like PCA fail when the data lies on a curved manifold. Non-linear techniques assume that high-dimensional data is embedded in a low-dimensional manifold. t-SNE and UMAP are the two most prominent modern algorithms for visualizing high-dimensional data in 2D or 3D. They excel at preserving local structure (neighborhoods) and are ubiquitous in exploratory data analysis for biology, NLP, and computer vision.

This figure shows the typical output of t-SNE or UMAP: a 2D scatter plot where distinct clusters are clearly separated. The three large ellipses (blue, orange, and green) represent groups of data points that are close to each other in the original high-dimensional space. For example, in a single-cell RNA-seq experiment, these clusters might correspond to different cell types (e.g., T-cells, B-cells, and natural killer cells). The two red points in the corners are outliers that are distinct from all clusters. The key insight is that the high-dimensional relationships (which points are neighbors) are preserved in the low-dimensional embedding. t-SNE and UMAP achieve this by converting distances into probabilities and then minimizing the divergence between the high-dimensional and low-dimensional probability distributions. This makes them invaluable for exploratory data analysis, where the goal is to visually identify patterns that are invisible in the original high-dimensional space. UMAP often produces tighter clusters and better preserves global distances than t-SNE, but both are sensitive to hyperparameters like perplexity or n_neighbors.

4.1 t-Distributed Stochastic Neighbor Embedding (t-SNE)

t-SNE converts high-dimensional Euclidean distances into conditional probabilities. The similarity of point j to point i is:

In the low-dimensional space, t-SNE uses a Student-t distribution (with one degree of freedom):

It minimizes the Kullback-Leibler (KL) divergence:

The gradient of the KL divergence with respect to the low-dimensional coordinates y_i is:

The heavy-tailed Student-t distribution in the low-dimensional space alleviates the "crowding problem" by allowing points to be placed farther apart without incurring a large penalty. The perplexity parameter, which can be thought of as the effective number of neighbors, governs the balance between local and global structure. t-SNE is widely used for visualization, but it is computationally expensive for large datasets due to the O(n²) cost of computing all pairwise affinities. The Barnes-Hut approximation reduces this to O(n log n) and makes it feasible for datasets up to ~100,000 points.

4.2 Uniform Manifold Approximation and Projection (UMAP)

UMAP constructs a fuzzy simplicial complex representation of the data and finds a low-dimensional embedding with a similar structure. It minimizes a cross-entropy loss:

UMAP is generally faster than t-SNE and better preserves global structure.

UMAP is grounded in Riemannian geometry and algebraic topology, giving it a stronger theoretical foundation than t-SNE. It assumes that the data is uniformly distributed on a Riemannian manifold and estimates the local metric using nearest-neighbor distances. The low-dimensional embedding is optimized using stochastic gradient descent, making it highly scalable. UMAP's key parameters, n_neighbors and min_dist, allow fine control over the preservation of local vs. global structure. It has become the default visualization tool for large biological datasets, such as single-cell RNA-seq with millions of cells, due to its speed and ability to retain meaningful global structure.

4.3 Key Differences and Examples

In single-cell RNA-seq data, t-SNE and UMAP are the de facto tools for identifying cell subtypes. UMAP often provides a more interpretable embedding, with clusters arranged to reflect developmental lineages, while t-SNE tends to separate clusters equally regardless of global relationships.

For example, in a dataset of hematopoietic stem cells differentiating into various blood cell types, UMAP often places progenitor cells in a central location with mature cell types radiating outward, reflecting the biological trajectory. t-SNE, on the other hand, may spread clusters apart without preserving the continuous transitions. This difference arises because t-SNE's cost function focuses on local similarities, while UMAP's cross-entropy loss balances local and global structure. In practice, both methods are used in conjunction: t-SNE for detailed cluster inspection and UMAP for a broader view of the data landscape. Researchers often run multiple perplexities or n_neighbors values to ensure the stability of their findings.

Applications

• Visualization of high-dimensional genomic data.
• Exploratory analysis of image embeddings.
• Anomaly detection.
• Preprocessing for clustering algorithms.

Strengths and limitations