Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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

DerivationProof
  1. ∥A−B∥2 ≥ ∥(A−B)w∥=∥Aw∥=(∑j≤k+1σj2(vj⊤w)2)1/2 ≥ σk+1\norm{A-B}_2\ \ge\ \norm{(A-B)\mathbf w}=\norm{A\mathbf w}=\Big(\sum_{j\le k+1}\sigma_j^2(\mathbf v_j^\top\mathbf w)^2\Big)^{1/2}\ \ge\ \sigma_{k+1}

    Spectral norm. Since rank⁡B≤k\rank B\le k, ker⁡B\ker B has dimension at least d−kd-k, so it meets the (k+1)(k+1)-dimensional span of v1,…,vk+1\mathbf v_1,\dots,\mathbf v_{k+1} in some unit vector w\mathbf w. On that span AA stretches every vector by at least σk+1\sigma_{k+1}:

  2. σi+k(A)≤σi(A−B)for all i≥1\sigma_{i+k}(A)\le\sigma_i(A-B)\qquad\text{for all }i\ge1

    Weyl's inequality for singular values, σi+j−1(X+Y)≤σi(X)+σj(Y)\sigma_{i+j-1}(X+Y)\le\sigma_i(X)+\sigma_j(Y), follows from the same subspace argument. Apply it with X=A−BX=A-B, Y=BY=B and j=k+1j=k+1, where σk+1(B)=0\sigma_{k+1}(B)=0:

  3. ∥A−B∥F2=∑i≥1σi(A−B)2 ≥ ∑i≥1σi+k(A)2=∑j>kσj2\norm{A-B}_F^2=\sum_{i\ge1}\sigma_i(A-B)^2\ \ge\ \sum_{i\ge1}\sigma_{i+k}(A)^2=\sum_{j>k}\sigma_j^2

    Frobenius norm. Sum the squares; equality holds for B=AkB=A_k:

  4. min⁡rank⁡B≤k∥X~−B∥F2=∥X~−X~VkVk⊤∥F2=n∑j>kλj\min_{\rank B\le k}\norm{\tilde X-B}_F^2=\norm{\tilde X-\tilde XV_kV_k^\top}_F^2=n\sum_{j>k}\lambda_j

    PCA. For centered data X~\tilde X, the best rank-kk approximation is X~VkVk⊤\tilde XV_kV_k^\top, the projection onto the top kk principal directions, with squared error ∑j>kσj2=n∑j>kλj\sum_{j>k}\sigma_j^2=n\sum_{j>k}\lambda_j. No other rank-kk approximation, in particular no other linear encoding into kk 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: x=Wz+μ+ε\mathbf x=W\mathbf z+\boldsymbol\mu+\boldsymbol\varepsilon with z∼N(0,Ik)\mathbf z\sim\mathcal N(\mathbf 0,I_k) and ε∼N(0,σ2Id)\boldsymbol\varepsilon\sim\mathcal N(\mathbf 0,\sigma^2I_d). The maximum-likelihood solution is σ2=1d−k∑j>kλj\sigma^2=\frac1{d-k}\sum_{j>k}\lambda_j, the average discarded eigenvalue, and W=Uk(Λk−σ2I)1/2RW=U_k(\Lambda_k-\sigma^2I)^{1/2}R for any rotation RR: 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 O(n3)\order{n^3} cost (Kernels & Support Vector Machines).

High-dimensional PCA: when the sample covariance lies

Let x1,…,xn\mathbf x_1,\dots,\mathbf x_n be i.i.d. N(0,Σ)\mathcal N(\mathbf 0,\Sigma) in Rd\R^d, with sample covariance S=1n∑ixixi⊤S=\frac1n\sum_i\mathbf x_i\mathbf x_i^\top. With dd fixed and n→∞n\to\infty, S→ΣS\to\Sigma. Modern data have dd comparable to nn, and then the eigenvalues of SS are systematically wrong, in a way random-matrix theory predicts exactly.

Predict before you look

Pure noise: Σ=I\Sigma=I, with as many dimensions as samples (d=nd=n, both large). Roughly how large is the top eigenvalue of the sample covariance?

Show the answer

4

λ+=(1+γ)2=(1+1)2=4\lambda_+=(1+\sqrt\gamma)^2=(1+1)^2=4, although every population eigenvalue is 1; the smallest sample eigenvalues approach 00. A naive analyst would report a "component" with four times the average variance in data that have no structure at all.

Think first With n=4,000n=4{,}000 samples in d=2,000d=2{,}000 dimensions (γ=0.5\gamma=0.5), a spike of strength β=2\beta=2 is planted. Predict the top sample eigenvalue and the squared overlap of v^\hat{\mathbf v} with v\mathbf v. Then: what happens with β=0.5\beta=0.5?

Theory: (1+2)(1+0.25)=3.75(1+2)(1+0.25)=3.75 and (1−0.125)/(1+0.25)=0.70(1-0.125)/(1+0.25)=0.70; one simulation gives 3.713.71 and 0.680.68. The eigenvalue is inflated (the population value is 1+β=31+\beta=3) and the eigenvector is only partly aligned. With β=0.5<0.5≈0.71\beta=0.5<\sqrt{0.5}\approx0.71, the top eigenvalue sits at the bulk edge (1+0.5)2≈2.91(1+\sqrt{0.5})^2\approx2.91 and the simulated squared overlap is 0.0030.003: 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 σ2(1+γ)2\sigma^2(1+\sqrt\gamma)^2 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 43n σ\tfrac4{\sqrt3}\sqrt n\,\sigma for singular values of a square noisy matrix (Gavish & Donoho, 2014). If the spike has only ss nonzero coordinates, exhaustive search detects it at strengths of order slog⁡d/n\sqrt{s\log d/n}, far below the spectral threshold, while known polynomial-time methods need about s2log⁡d/n\sqrt{s^2\log d/n}; 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, pj∣i∝exp⁡(−∥xi−xj∥2/2σi2)p_{j\mid i}\propto\exp\big(-\norm{\mathbf x_i-\mathbf x_j}^2/2\sigma_i^2\big), where each bandwidth σi\sigma_i is set by binary search so that the perplexity 2H(Pi)2^{H(P_i)}, an effective number of neighbors, equals a user value (typically 5–50); then pij=(pj∣i+pi∣j)/2np_{ij}=(p_{j\mid i}+p_{i\mid j})/2n. In the 2-D map, similarities use a heavy-tailed Student-tt kernel,

qij=wij∑l≠mwlm,wij=(1+∥yi−yj∥2)−1,q_{ij}=\frac{w_{ij}}{\sum_{l\ne m}w_{lm}},\qquad w_{ij}=\big(1+\norm{\mathbf y_i-\mathbf y_j}^2\big)^{-1},

and the map minimizes the KL divergence DKL(P ∥ Q)=∑i≠jpijlog⁡(pij/qij)\KL(P\,\|\,Q)=\sum_{i\ne j}p_{ij}\log(p_{ij}/q_{ij}) by gradient descent.

DerivationThe gradient: attraction and repulsion
  1. C=∑i≠jpijlog⁡pij−∑i≠jpijlog⁡wij+log⁡ZC=\sum_{i\ne j}p_{ij}\log p_{ij}-\sum_{i\ne j}p_{ij}\log w_{ij}+\log Z

    Since ∑pij=1\sum p_{ij}=1, the cost is a constant minus ∑pijlog⁡wij\sum p_{ij}\log w_{ij} plus log⁡Z\log Z, with Z=∑l≠mwlmZ=\sum_{l\ne m}w_{lm}:

  2. ∂C∂yi=4∑j(pij−qij) wij (yi−yj)\frac{\partial C}{\partial\mathbf y_i}=4\sum_j\big(p_{ij}-q_{ij}\big)\,w_{ij}\,(\mathbf y_i-\mathbf y_j)

    Differentiate, using ∂wij/∂yi=−2wij2(yi−yj)\partial w_{ij}/\partial\mathbf y_i=-2w_{ij}^2(\mathbf y_i-\mathbf y_j) and qij=wij/Zq_{ij}=w_{ij}/Z:

  3. ∂C∂yi=4∑jpijwij(yi−yj)⏟attraction−4∑jqijwij(yi−yj)⏟repulsion\frac{\partial C}{\partial\mathbf y_i}=\underbrace{4\sum_jp_{ij}w_{ij}(\mathbf y_i-\mathbf y_j)}_{\text{attraction}}-\underbrace{4\sum_jq_{ij}w_{ij}(\mathbf y_i-\mathbf y_j)}_{\text{repulsion}}

    Read it as forces: input neighbors (large pijp_{ij}) attract, and every point repels every other, with total repulsion normalized by ZZ. Computing the repulsion naively costs O(n2)\order{n^2} per iteration; Barnes–Hut trees bring it to O(nlog⁡n)\order{n\log n} (van der Maaten, 2014), and FFT interpolation lower still (Linderman et al., 2019).

  4. wij=(1+∥yi−yj∥2)−1≈∥yi−yj∥−2for distant pairsw_{ij}=\big(1+\norm{\mathbf y_i-\mathbf y_j}^2\big)^{-1}\approx\norm{\mathbf y_i-\mathbf y_j}^{-2}\quad\text{for distant pairs}

    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 wij≈∥yi−yj∥−2w_{ij}\approx\norm{\mathbf y_i-\mathbf y_j}^{-2}, 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 PP 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 kk-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 wij=wi→j+wj→i−wi→jwj→iw_{ij}=w_{i\to j}+w_{j\to i}-w_{i\to j}w_{j\to i}. The map uses similarities (1+a d2b)−1(1+a\,d^{2b})^{-1} and minimizes a cross-entropy between graph weights and map similarities by stochastic gradient descent with negative sampling, roughly linear in nn 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).

MethodPreservesObjectiveCostNew points
PCAglobal variance (linear)Eckart–Young, closed formO(ndk)\order{ndk} for kk componentsproject them
t-SNElocal neighborhoods at the perplexity scaleDKL(P∥Q)\KL(P\|Q), nonconvexO(nlog⁡n)\order{n\log n} per iterationno native map
UMAPlocal neighborhoods, some coarse global structurefuzzy cross-entropy with negative samplingabout O(n)\order{n} per epoch, plus approximate kk-NNapproximate transform
t-SNE and UMAP depend on the random seed and, strongly, on the initialization: starting from PCA preserves much more global structure (Kobak & Linderman, 2021).

What can be preserved: Johnson–Lindenstrauss and its limits

DerivationProof (Dasgupta & Gupta, 2003)
  1. k ∥f(u)∥2∥u∥2∼χk2,E∥f(u)∥2=∥u∥2\frac{k\,\norm{f(\mathbf u)}^2}{\norm{\mathbf u}^2}\sim\chi^2_k,\qquad\E\norm{f(\mathbf u)}^2=\norm{\mathbf u}^2

    Fix a vector u≠0\mathbf u\ne\mathbf 0. Each coordinate of AuA\mathbf u is N(0,∥u∥2)\mathcal N(0,\norm{\mathbf u}^2), independently, so the squared length of f(u)f(\mathbf u) is a scaled chi-squared variable with mean ∥u∥2\norm{\mathbf u}^2:

  2. Pr⁡[∣∥f(u)∥2∥u∥2−1∣>ε]≤2exp⁡(−k2(ε22−ε33))\Pr\Big[\Big|\frac{\norm{f(\mathbf u)}^2}{\norm{\mathbf u}^2}-1\Big|>\varepsilon\Big]\le2\exp\Big(-\frac k2\Big(\frac{\varepsilon^2}2-\frac{\varepsilon^3}3\Big)\Big)

    A Chernoff bound for χk2\chi^2_k (moment generating function (1−2s)−k/2(1-2s)^{-k/2}, optimized over ss) gives two-sided concentration:

  3. Pr⁡[some pair fails]≤(n2)⋅2n2=1−1n\Pr[\text{some pair fails}]\le\binom n2\cdot\frac2{n^2}=1-\frac1n

    Apply this to the (n2)\binom n2 difference vectors xi−xj\mathbf x_i-\mathbf x_j (linearity: f(xi)−f(xj)=f(xi−xj)f(\mathbf x_i)-f(\mathbf x_j)=f(\mathbf x_i-\mathbf x_j)). With the stated kk, each failure probability is at most 2/n22/n^2, and a union bound leaves success probability at least 1/n1/n:

  4. k=Θ(log⁡nε2)k=\Theta\Big(\frac{\log n}{\varepsilon^2}\Big)

    The bound is optimal: Larsen & Nelson (2017) showed that some nn-point sets need k=Ω(ε−2log⁡n)k=\Omega(\varepsilon^{-2}\log n) for any embedding into a Euclidean space with distortion 1+ε1+\varepsilon, linear or not.

Predict before you look

You want to preserve all pairwise squared distances among n=106n=10^6 points within ±10%\pm10\% (ε=0.1\varepsilon=0.1). What target dimension does the bound k≥4ln⁡n/(ε2/2−ε3/3)k\ge4\ln n/(\varepsilon^2/2-\varepsilon^3/3) require?

Show the answer

11842

ln⁡106≈13.82\ln10^6\approx13.82 and ε2/2−ε3/3≈0.00467\varepsilon^2/2-\varepsilon^3/3\approx0.00467, so k≥55.3/0.00467≈11,800k\ge55.3/0.00467\approx11{,}800, whatever the original dimension, be it 10510^5 or 10910^9. The flip side: with k=2k=2, 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. nn equidistant points (a regular simplex) need n−1n-1 dimensions to embed isometrically, and in the plane a packing argument forces distortion of order n\sqrt n: images that are pairwise at least mm apart need a disk of diameter of order mnm\sqrt n. 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 kk-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-kk approximation in spectral and Frobenius norms, so PCA's reconstruction error is n∑j>kλjn\sum_{j>k}\lambda_j; probabilistic PCA adds a likelihood and kernel PCA nonlinearity.
  • With d/n→γd/n\to\gamma, pure-noise eigenvalues fill [σ2(1−γ)2, σ2(1+γ)2][\sigma^2(1-\sqrt\gamma)^2,\ \sigma^2(1+\sqrt\gamma)^2], so a top eigenvalue of 4 can be pure noise when d=nd=n.
  • BBP: a spike is visible only if β>γ\beta>\sqrt\gamma, and even then its eigenvalue is inflated to (1+β)(1+γ/β)(1+\beta)(1+\gamma/\beta) and its eigenvector's squared overlap is only (1−γ/β2)/(1+γ/β)(1-\gamma/\beta^2)/(1+\gamma/\beta).
  • t-SNE minimizes DKL(P∥Q)\KL(P\|Q) with a Student-tt map kernel: attraction between input neighbors, global repulsion. UMAP is a graph-based relative; both keep neighborhoods, not cluster sizes or gaps.
  • Johnson–Lindenstrauss: O(ε−2log⁡n)\order{\varepsilon^{-2}\log n} random dimensions preserve all pairwise distances, independently of dd, 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.

Question 1

A matrix has singular values 5,3,2,15,3,2,1. What is the Frobenius-norm error of its best rank-2 approximation?

  1. 11
  2. 22
  3. 5\sqrt5
  4. 33
Show the answer

C. 5\sqrt5

Eckart–Young: the error is (∑j>2σj2)1/2=4+1=5\big(\sum_{j>2}\sigma_j^2\big)^{1/2}=\sqrt{4+1}=\sqrt5, attained by truncating the SVD. The spectral-norm error would be σ3=2\sigma_3=2.

Question 2

Pure noise with Σ=I\Sigma=I and d=n/4d=n/4, both large. Where do the eigenvalues of the sample covariance lie?

  1. All close to 1
  2. Spread over about [0.25, 2.25][0.25,\,2.25]
  3. Spread over about [0, 4][0,\,4]
  4. All close to 0.25
Show the answer

B. Spread over about [0.25, 2.25][0.25,\,2.25]

Marchenko–Pastur with γ=1/4\gamma=1/4: λ±=(1±12)2\lambda_\pm=(1\pm\tfrac12)^2, so [0.25,2.25][0.25,2.25]. The spread is pure sampling noise; components inside it are indistinguishable from it.

Question 3

In the spiked covariance model with d/n→γd/n\to\gamma, the spike strength satisfies β<γ\beta<\sqrt\gamma. What does the top sample eigenvector tell you about the spike direction v\mathbf v?

  1. It converges to v\mathbf v, only more slowly
  2. Its squared overlap with v\mathbf v converges to β\beta
  3. It is biased but still informative, with overlap 12\tfrac12
  4. Asymptotically nothing: its overlap with v\mathbf v tends to zero
Show the answer

D. Asymptotically nothing: its overlap with v\mathbf v tends to zero

Below the BBP threshold the top eigenvalue sticks to the bulk edge (1+γ)2(1+\sqrt\gamma)^2 and the eigenvector is asymptotically orthogonal to v\mathbf v. Above it, the squared overlap is (1−γ/β2)/(1+γ/β)(1-\gamma/\beta^2)/(1+\gamma/\beta), which rises from 0 at the threshold.

Question 4

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?

  1. Points within each cluster are mutual near neighbors in the input space; the sizes and gaps are not reliable
  2. A has three times the variance of B
  3. A and C are the most dissimilar groups in the data
  4. 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).