PCA, t-SNE & UMAP
Finding low-dimensional structure in high-dimensional data.
PCA is the oldest tool in data analysis and still the first to reach for, yet in high dimensions the sample covariance misleads in precise, predictable ways. t-SNE and UMAP draw beautiful maps that are easy to misread. This lesson proves what each method preserves, computes when PCA's components are signal and when they are noise, and shows what no low-dimensional picture can do.
What you’ll learn
- Prove the Eckart–Young–Mirsky theorem and use it to characterize PCA as optimal low-rank approximation; relate it to probabilistic and kernel PCA.
- State the Marchenko–Pastur law and the BBP phase transition, and use them to decide which sample eigenvalues and eigenvectors carry signal.
- Derive the t-SNE objective and gradient as attraction and repulsion, explain perplexity and the crowding problem, and contrast UMAP's construction.
- Prove the Johnson–Lindenstrauss lemma and explain the limits on what low-dimensional embeddings can preserve.
PCA as optimal low-rank approximation
Spectral norm. Since , has dimension at least , so it meets the -dimensional span of in some unit vector . On that span stretches every vector by at least :
Weyl's inequality for singular values, , follows from the same subspace argument. Apply it with , and , where :
Frobenius norm. Sum the squares; equality holds for :
PCA. For centered data , the best rank- approximation is , the projection onto the top principal directions, with squared error . No other rank- approximation, in particular no other linear encoding into numbers followed by linear decoding, reconstructs the data better in these norms; nonlinear decoders are not covered by the theorem.
Probabilistic PCA (Tipping & Bishop, 1999) gives PCA a likelihood: with and . The maximum-likelihood solution is , the average discarded eigenvalue, and for any rotation : the principal subspace again, now with a noise model that supports model selection, missing data and mixtures of PCAs.
Kernel PCA (Schölkopf, Smola & Müller, 1998) runs PCA in a feature space through the centered kernel matrix: its top eigenvectors give nonlinear components, at cost (Kernels & Support Vector Machines).
High-dimensional PCA: when the sample covariance lies
Let be i.i.d. in , with sample covariance . With fixed and , . Modern data have comparable to , and then the eigenvalues of are systematically wrong, in a way random-matrix theory predicts exactly.
Pure noise: , with as many dimensions as samples (, both large). Roughly how large is the top eigenvalue of the sample covariance?
Show the answer
4
, although every population eigenvalue is 1; the smallest sample eigenvalues approach . A naive analyst would report a "component" with four times the average variance in data that have no structure at all.
Think first With samples in dimensions (), a spike of strength is planted. Predict the top sample eigenvalue and the squared overlap of with . Then: what happens with ?
Theory: and ; one simulation gives and . The eigenvalue is inflated (the population value is ) and the eigenvector is only partly aligned. With , the top eigenvalue sits at the bulk edge and the simulated squared overlap is : PCA sees nothing, although the spike adds 50% variance in its direction.
Practical consequences. Eigenvalues inside the Marchenko–Pastur bulk are indistinguishable from noise, so components above are the candidates for signal (permutation-based "parallel analysis", Horn, 1965, is the empirical version). Even above the threshold, sample eigenvalues are biased upward and eigenvectors misaligned, which motivates optimal shrinkage of eigenvalues (Donoho, Gavish & Johnstone, 2018) and the hard threshold for singular values of a square noisy matrix (Gavish & Donoho, 2014). If the spike has only nonzero coordinates, exhaustive search detects it at strengths of order , far below the spectral threshold, while known polynomial-time methods need about ; reductions from the planted-clique problem suggest this statistical–computational gap is real (Berthet & Rigollet, 2013).
Neighbor embeddings: t-SNE and UMAP
t-SNE (van der Maaten & Hinton, 2008), refining SNE (Hinton & Roweis, 2002), matches neighbor distributions. In the input space, , where each bandwidth is set by binary search so that the perplexity , an effective number of neighbors, equals a user value (typically 5–50); then . In the 2-D map, similarities use a heavy-tailed Student- kernel,
and the map minimizes the KL divergence by gradient descent.
Since , the cost is a constant minus plus , with :
Differentiate, using and :
Read it as forces: input neighbors (large ) attract, and every point repels every other, with total repulsion normalized by . Computing the repulsion naively costs per iteration; Barnes–Hut trees bring it to (van der Maaten, 2014), and FFT interpolation lower still (Linderman et al., 2019).
The heavy tail solves the crowding problem: a 2-D map has too little room to place all moderately distant neighbors at their true distances, and for far-apart points , so moderately dissimilar points can sit far apart at little cost. That is also why gaps between clusters in t-SNE plots are exaggerated and uninformative.
In practice t-SNE starts with early exaggeration, multiplying by a factor such as 12 for the first few hundred iterations. In that phase it provably behaves like spectral clustering and separates well-clustered data into distinct groups (Arora, Hu & Kothari, 2018; Linderman & Steinerberger, 2019).
UMAP (McInnes, Healy & Melville, 2018) builds a weighted -nearest-neighbor graph with locally adaptive scales, so that every point is connected to its nearest neighbor with weight 1, and symmetrizes it by the fuzzy union . The map uses similarities and minimizes a cross-entropy between graph weights and map similarities by stochastic gradient descent with negative sampling, roughly linear in per epoch. Its motivation comes from fuzzy simplicial sets, but its sampling scheme does not minimize its stated loss (Damrich & Hamprecht, 2021). Empirically, UMAP behaves much like t-SNE with stronger attraction; varying the exaggeration traces a spectrum from t-SNE through UMAP-like maps to Laplacian eigenmaps (Böhm, Berens & Kobak, 2022).
| Method | Preserves | Objective | Cost | New points |
|---|---|---|---|---|
| PCA | global variance (linear) | Eckart–Young, closed form | for components | project them |
| t-SNE | local neighborhoods at the perplexity scale | , nonconvex | per iteration | no native map |
| UMAP | local neighborhoods, some coarse global structure | fuzzy cross-entropy with negative sampling | about per epoch, plus approximate -NN | approximate transform |
What can be preserved: Johnson–Lindenstrauss and its limits
Fix a vector . Each coordinate of is , independently, so the squared length of is a scaled chi-squared variable with mean :
A Chernoff bound for (moment generating function , optimized over ) gives two-sided concentration:
Apply this to the difference vectors (linearity: ). With the stated , each failure probability is at most , and a union bound leaves success probability at least :
The bound is optimal: Larsen & Nelson (2017) showed that some -point sets need for any embedding into a Euclidean space with distortion , linear or not.
You want to preserve all pairwise squared distances among points within (). What target dimension does the bound require?
Show the answer
11842
and , so , whatever the original dimension, be it or . The flip side: with , distances among more than a handful of points cannot all be preserved, so a 2-D picture must sacrifice something.
Hard limits follow from geometry. equidistant points (a regular simplex) need dimensions to embed isometrically, and in the plane a packing argument forces distortion of order : images that are pairwise at least apart need a disk of diameter of order . Any 2-D picture of rich data is therefore a choice of what to distort: PCA keeps large distances on average, neighbor embeddings keep small ones.
When data lie near a smooth low-dimensional manifold, nonlinear spectral methods can unfold it: Isomap estimates geodesic distances through a -nearest-neighbor graph and applies classical multidimensional scaling (Tenenbaum, de Silva & Langford, 2000); locally linear embedding (Roweis & Saul, 2000), Laplacian eigenmaps (Belkin & Niyogi, 2003) and diffusion maps (Coifman & Lafon, 2006) use graph Laplacians, which converge to the manifold's Laplace–Beltrami operator as the sample grows.
Key takeaways
- Eckart–Young–Mirsky: truncating the SVD gives the best rank- approximation in spectral and Frobenius norms, so PCA's reconstruction error is ; probabilistic PCA adds a likelihood and kernel PCA nonlinearity.
- With , pure-noise eigenvalues fill , so a top eigenvalue of 4 can be pure noise when .
- BBP: a spike is visible only if , and even then its eigenvalue is inflated to and its eigenvector's squared overlap is only .
- t-SNE minimizes with a Student- map kernel: attraction between input neighbors, global repulsion. UMAP is a graph-based relative; both keep neighborhoods, not cluster sizes or gaps.
- Johnson–Lindenstrauss: random dimensions preserve all pairwise distances, independently of , and that is optimal; two dimensions cannot, so every picture chooses what to distort.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A matrix has singular values . What is the Frobenius-norm error of its best rank-2 approximation?
Show the answer
C.
Eckart–Young: the error is , attained by truncating the SVD. The spectral-norm error would be .
Pure noise with and , both large. Where do the eigenvalues of the sample covariance lie?
- All close to 1
- Spread over about
- Spread over about
- All close to 0.25
Show the answer
B. Spread over about
Marchenko–Pastur with : , so . The spread is pure sampling noise; components inside it are indistinguishable from it.
In the spiked covariance model with , the spike strength satisfies . What does the top sample eigenvector tell you about the spike direction ?
- It converges to , only more slowly
- Its squared overlap with converges to
- It is biased but still informative, with overlap
- Asymptotically nothing: its overlap with tends to zero
Show the answer
D. Asymptotically nothing: its overlap with tends to zero
Below the BBP threshold the top eigenvalue sticks to the bulk edge and the eigenvector is asymptotically orthogonal to . Above it, the squared overlap is , which rises from 0 at the threshold.
In a t-SNE plot, cluster A is drawn three times larger than cluster B and far away from cluster C. What can you safely conclude?
- Points within each cluster are mutual near neighbors in the input space; the sizes and gaps are not reliable
- A has three times the variance of B
- A and C are the most dissimilar groups in the data
- A contains three times as many points as B
Show the answer
A. Points within each cluster are mutual near neighbors in the input space; the sizes and gaps are not reliable
t-SNE preserves neighborhoods at the perplexity scale. Its per-point bandwidths equalize densities, which erases differences in cluster spread, and the heavy-tailed kernel exaggerates gaps, so cluster sizes and between-cluster distances carry little meaning.
Further reading
- C. Eckart & G. Young, "The approximation of one matrix by another of lower rank," Psychometrika 1(3), 211–218 (1936).
- J. Baik, G. Ben Arous & S. Péché, "Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices," Annals of Probability 33(5), 1643–1697 (2005).
- L. van der Maaten & G. Hinton, "Visualizing data using t-SNE," Journal of Machine Learning Research 9, 2579–2605 (2008).
- L. McInnes, J. Healy & J. Melville, "UMAP: Uniform manifold approximation and projection for dimension reduction," arXiv:1802.03426 (2018).
- R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science (Cambridge University Press, 2018).