Part IV · Unsupervised learning | principal component analysis by maximum variance and minimum error, the SVD, eigenfaces, scree plots and the Eckart–Young theorem, PCA of human genotypes, probabilistic PCA and factor analysis, random projections and the Johnson–Lindenstrauss lemma, matrix factorisation for recommendations | reading: Hastie, Tibshirani & Friedman, The Elements of Statistical Learning (2nd ed.), §14.5; Bishop, Pattern Recognition and Machine Learning (2006), ch. 12; Tipping & Bishop (1999); Dasgupta & Gupta (2003); Koren, Bell & Volinsky (2009) | nonlinear methods follow in Lecture 16b
A 64×64 grey-scale photograph is a point in 4,096 dimensions; a genotype at 9,000 sites, a point in 9,000. Lecture 14 showed that such spaces are hostile: distances concentrate and densities cannot be estimated. But real data rarely fill them: faces lie near a much lower-dimensional shape. Dimension reduction describes each point by a few coordinates on that shape.
The linear methods of this lecture look for a flat subspace (a line, plane or higher analogue through the origin) and project each point onto it, like a shadow under an overhead lamp. Lecture 16b follows curved shapes, with Isomap, Laplacian eigenmaps, t-SNE, UMAP and autoencoders.
By the end you should be able to compute principal components by the SVD and prove that maximum variance and minimum reconstruction error agree; use the Eckart–Young theorem; choose a dimension; read a PCA of genotypes and explain its use against confounding; say when probabilistic PCA and factor analysis differ; prove the Johnson–Lindenstrauss lemma; and fit a regularised low-rank model to a sparse ratings matrix.
Take the Old Faithful eruptions of Lecture 14 as points (duration, waiting time). Projecting onto a line through the mean replaces two numbers by one. Which line: the one along which the projections spread most, or the one the points are closest to? They are the same line, in any dimension.
Let \(x_1,\dots,x_n\in\mathbb R^d\) have mean \(\bar x\), and let \(X_c\) be the \(n\times d\) matrix with rows \(x_i-\bar x\).
If \(X_c=U\Sigma V^\top\) is the singular value decomposition, then
$$V=(v_1,\dots,v_d),\qquad\lambda_j=\frac{\sigma_j^2}{n-1},\qquad\text{scores}=U\Sigma.$$The principal directions are the axes of the data cloud, longest first, like the axes of a rugby ball; each eigenvalue is the variance along its axis.
Let \(W\in\mathbb R^{d\times k}\) have orthonormal columns and let \(P=WW^\top\) be the orthogonal projection onto their span. Then
$$\underbrace{\frac1{n-1}\sum_i\lVert P(x_i-\bar x)\rVert^2}_{\text{variance kept}}+\underbrace{\frac1{n-1}\sum_i\lVert(I-P)(x_i-\bar x)\rVert^2}_{\text{reconstruction error}}=\operatorname{tr}S=\sum_{j=1}^d\lambda_j.$$Hence maximising the variance kept is the same as minimising the reconstruction error. Both are achieved by the span of \(v_1,\dots,v_k\), with variance kept
$$\lambda_1+\dots+\lambda_k.$$For each \(i\), the vectors \(P(x_i-\bar x)\) and \((I-P)(x_i-\bar x)\) are orthogonal, so by Pythagoras their squared lengths add to \(\lVert x_i-\bar x\rVert^2\).
Summing and dividing by \(n-1\) gives \(\operatorname{tr}S\), which does not depend on \(W\). This proves the identity, so the two problems have the same solutions.
The variance kept is
$$\frac1{n-1}\sum_i\lVert W^\top(x_i-\bar x)\rVert^2=\operatorname{tr}(W^\top SW).$$Write \(S=\sum_j\lambda_jv_jv_j^\top\). Then
$$\operatorname{tr}(W^\top SW)=\sum_j\lambda_jc_j,\qquad c_j=\lVert W^\top v_j\rVert^2.$$Each \(c_j\in[0,1]\), being the squared length of the projection of a unit vector, and \(\sum_jc_j=\operatorname{tr}(WW^\top)=k\).
A sum \(\sum_j\lambda_jc_j\) with weights in \([0,1]\) adding to \(k\) is largest when weight 1 goes to the \(k\) largest \(\lambda_j\). This gives \(\lambda_1+\dots+\lambda_k\), attained by \(W=(v_1,\dots,v_k)\). \(\square\)
In practice one uses the SVD of \(X_c\), never \(S\): it is more accurate (forming \(X_c^\top X_c\) squares the condition number), and when \(n<d\), as with faces, it works in the small dimension.
Ten photographs of each of 40 people, taken between 1992 and 1994 at Olivetti Research Laboratory (later AT&T Laboratories Cambridge), with varying lighting, expression and glasses (the "ORL" or "AT&T" database; Samaria and Harter, 1994). We use Sam Roweis's 64×64-pixel grey-scale version distributed with scikit-learn, from the PNG copy in the GitHub repository lloydmeta/Olivetti-PNG, as scikit-learn's own source was not reachable from the build environment. Images are ordered by person, ten at a time.
# Eigenfaces: PCA of 400 face images by the singular value decomposition import numpy as np from PIL import Image faces = np.array([np.asarray(Image.open(f'data/olivetti/images/image-{i}.png'), float) / 255 for i in range(400)]) X = faces.reshape(400, -1); n, d = X.shape # 400 images of 64 x 64 = 4,096 pixels mu = X.mean(0); Xc = X - mu U, s, Vt = np.linalg.svd(Xc, full_matrices=False) # Xc = U diag(s) Vt; rows of Vt are the eigenfaces lam = s**2 / (n - 1) # eigenvalues of the sample covariance matrix print(f"{n} faces x {d} pixels; rank of the centred data {np.sum(s > 1e-8 * s[0])}") C = Xc.T @ Xc / (n - 1); ev = np.linalg.eigvalsh(C)[::-1] # the slow way: eigenvalues of the 4096 x 4096 covariance print(f"top 3 eigenvalues via SVD {np.round(lam[:3], 3)}, via the covariance matrix {np.round(ev[:3], 3)}") total = lam.sum() for k in [1, 5, 20, 50, 100, 200]: P = Vt[:k]; Z = Xc @ P.T # scores on the first k components var_kept = (Z**2).sum() / (n - 1); recon = ((Xc - Z @ P)**2).sum() / (n - 1) print(f"k = {k:3d}: variance kept {var_kept:7.3f} ({var_kept / total:5.1%}), reconstruction error {recon:7.3f}, " f"sum {var_kept + recon:.3f}")
400 faces x 4096 pixels; rank of the centred data 399 top 3 eigenvalues via SVD [26.256 18.063 10.236], via the covariance matrix [26.256 18.063 10.236] k = 1: variance kept 26.256 (21.3%), reconstruction error 97.252, sum 123.508 k = 5: variance kept 65.510 (53.0%), reconstruction error 57.998, sum 123.508 k = 20: variance kept 93.207 (75.5%), reconstruction error 30.301, sum 123.508 k = 50: variance kept 107.348 (86.9%), reconstruction error 16.160, sum 123.508 k = 100: variance kept 115.182 (93.3%), reconstruction error 8.326, sum 123.508 k = 200: variance kept 120.730 (97.8%), reconstruction error 2.778, sum 123.508
The SVD and the 4,096×4,096 covariance give the same eigenvalues (26.256, 18.063, 10.236), and variance kept plus error is 123.508 at every \(k\) (Theorem 16.1). The rank is 399, not 400, because centring removes one dimension. Five components keep 53.0% of the variance, 50 keep 86.9%, 200 keep 97.8%.
Two-dimensional data have covariance matrix \(\begin{pmatrix}4&0\\0&1\end{pmatrix}\). What fraction of the total variance does the first principal component keep?
Karl Pearson posed the minimum-error problem ("lines and planes of closest fit", 1901). Harold Hotelling (1933) gave the maximum-variance version, the name and an iterative method, motivated by psychological test scores. The SVD goes back to Beltrami and Jordan in the 1870s; Golub and Kahan's 1965 algorithm made it practical. Sirovich and Kirby applied PCA to faces in 1987, and Turk and Pentland's "Eigenfaces for recognition" (1991) made it the first widely used face recogniser: project a new face onto the eigenfaces and find the nearest known face.
How many components to keep? A scree plot (Cattell, 1966, after the rubble below a cliff) shows \(\lambda_j\) against \(j\); keep the components before it flattens. The explained variance
$$\frac{\lambda_1+\dots+\lambda_k}{\sum_j\lambda_j}$$gives a threshold rule (keep 90% or 95%). Whatever \(k\), the PCA reconstruction is the best of its rank, in the Frobenius norm \(\lVert A\rVert_F\) (root sum of squared entries) and the spectral norm \(\lVert A\rVert_2\) (largest stretch of a unit vector).
Let \(A\) be an \(n\times d\) matrix with SVD and truncation
$$A=\sum_{j}\sigma_ju_jv_j^\top,\qquad A_k=\sum_{j\le k}\sigma_ju_jv_j^\top,$$where \(\sigma_1\ge\sigma_2\ge\dots\). Then for every matrix \(B\) of rank at most \(k\),
$$\lVert A-B\rVert_F^2\;\ge\;\lVert A-A_k\rVert_F^2=\sum_{j>k}\sigma_j^2,$$and the same holds in the spectral norm, with
$$\lVert A-B\rVert_2\;\ge\;\lVert A-A_k\rVert_2=\sigma_{k+1}.$$(Eckart and Young, 1936; Mirsky, 1960.)
Spectral norm. If \(\operatorname{rank}B\le k\), its null space has dimension at least \(d-k\). So it meets the \((k+1)\)-dimensional span of \(v_1,\dots,v_{k+1}\) in some unit vector \(w\).
Since \(w\) is a combination of the first \(k+1\) right singular vectors,
$$\lVert(A-B)w\rVert=\lVert Aw\rVert\ge\sigma_{k+1}.$$Hence \(\lVert A-B\rVert_2\ge\sigma_{k+1}=\lVert A-A_k\rVert_2\).
Frobenius norm. Weyl's inequality for singular values gives
$$\sigma_{i+j-1}(A)\le\sigma_i(A-B)+\sigma_j(B).$$Take \(j=k+1\), where \(\sigma_{k+1}(B)=0\). Then \(\sigma_i(A-B)\ge\sigma_{i+k}(A)\) for every \(i\).
Squaring and summing over \(i\) gives \(\lVert A-B\rVert_F^2\ge\sum_{j>k}\sigma_j^2\). Equality at \(A_k\) follows from orthonormality of the singular vectors. \(\square\)
# Choosing the dimension, and Eckart-Young: no rank-k matrix approximates the faces better than PCA cum = np.cumsum(lam) / total for q in [0.5, 0.8, 0.9, 0.95, 0.99]: print(f"components needed for {q:.0%} of the variance: {np.searchsorted(cum, q) + 1}") rng = np.random.default_rng(0) for k in [10, 50]: Xk = (U[:, :k] * s[:k]) @ Vt[:k] err = np.sum((Xc - Xk)**2) Q = np.linalg.qr(rng.standard_normal((d, k)))[0] # a random k-dimensional subspace, for comparison err_r = np.sum((Xc - Xc @ Q @ Q.T)**2) print(f"rank {k}: ||X - X_k||_F^2 = {err:.2f}; sum of discarded s_i^2 = {np.sum(s[k:]**2):.2f}; " f"projection on a random {k}-dim subspace: {err_r:.2f}")
components needed for 50% of the variance: 5 components needed for 80% of the variance: 28 components needed for 90% of the variance: 69 components needed for 95% of the variance: 127 components needed for 99% of the variance: 267 rank 10: ||X - X_k||_F^2 = 17523.60; sum of discarded s_i^2 = 17523.60; projection on a random 10-dim subspace: 49139.88 rank 50: ||X - X_k||_F^2 = 6447.95; sum of discarded s_i^2 = 6447.95; projection on a random 50-dim subspace: 48718.69
The faces need 5 components for half the variance, 28 for 80%, 69 for 90%, 127 for 95% and 267 for 99%. With no elbow, the choice depends on the purpose. The rank-10 squared error equals the sum of the discarded squared singular values (17,523.60), as Eckart–Young says; a random 10-dimensional subspace leaves 49,139.88, close to the total (see Section 4).
PCA's most consequential application may be in human genetics. A genotype at a single-nucleotide polymorphism (SNP) is the number of copies, 0, 1 or 2, of the less common allele. Allele frequencies differ slightly between populations; each SNP says almost nothing about ancestry, but thousands of small nudges add up, as many slightly biased coin tosses reveal a bias no single toss could.
Genotypes of 279 people at 9,088 SNPs from Phase II of the International HapMap Project: Yoruba from Ibadan, Nigeria (YRI); Utah residents with northern and western European ancestry (CEU); Han Chinese from Beijing (HCB); and Japanese from Tokyo (JPT). The sample ships with the SNPRelate R package (Zheng et al., 2012; zhengxwen/SNPRelate on GitHub, GPL-3) in GDS format; as R was not available, data/hapmap_from_gds.py extracts the genotypes from the file's bytes, and the code below checks them. The plan called for the 1000 Genomes Project, HapMap's successor, whose files could not be downloaded from the build environment. YRI and CEU were collected as parent–child trios, so some individuals are closely related.
# PCA of genotypes: 279 HapMap individuals at 9,088 SNPs (extracted by data/hapmap_from_gds.py) H = np.load('data/hapmap.npz'); G = H['G'].astype(float); pop = H['pop'] G[G == 3] = np.nan; p = np.nanmean(G, 0) / 2 # allele frequency of each SNP keep = (p > 0.01) & (p < 0.99) Gs = (np.where(np.isnan(G), 2 * p, G) - 2 * p)[:, keep] / np.sqrt(2 * p * (1 - p))[keep] # Patterson et al. (2006) Ug, sg, Vg = np.linalg.svd(Gs, full_matrices=False); PC = Ug * sg print(f"{Gs.shape[0]} individuals, {Gs.shape[1]} SNPs after removing near-monomorphic ones; missing genotypes {np.isnan(G).mean():.2%}") print("variance explained by PCs 1-6:", " ".join(f"{v:.1%}" for v in sg[:6]**2 / np.sum(sg**2))) for g in ['YRI', 'CEU', 'HCB', 'JPT']: m = pop == g; print(f" {g}: n = {m.sum():2d}, mean PC1 {PC[m, 0].mean():+6.1f}, PC2 {PC[m, 1].mean():+6.1f}, " f"PC3 {PC[m, 2].mean():+6.1f}, PC4 {PC[m, 3].mean():+6.1f}") from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import cross_val_score for k in [2, 4, 10]: acc = cross_val_score(KNeighborsClassifier(5), PC[:, :k], pop, cv=5).mean() print(f"5-NN population accuracy from the first {k:2d} PCs (5-fold CV): {acc:.3f}") ea = np.isin(pop, ['HCB', 'JPT']); Ue = np.linalg.svd(Gs[ea] - Gs[ea].mean(0), full_matrices=False)[0][:, 0] sep = max(np.mean((Ue > 0) == (pop[ea] == 'JPT')), np.mean((Ue > 0) != (pop[ea] == 'JPT'))) print(f"PCA of the 94 East Asian individuals alone: sign of PC1 separates HCB from JPT for {sep:.1%} of them")
279 individuals, 9039 SNPs after removing near-monomorphic ones; missing genotypes 0.40% variance explained by PCs 1-6: 12.4% 5.8% 1.0% 0.9% 0.9% 0.7% YRI: n = 93, mean PC1 -49.4, PC2 +4.4, PC3 +0.0, PC4 -0.1 CEU: n = 92, mean PC1 +19.0, PC2 -31.7, PC3 +0.1, PC4 +0.1 HCB: n = 47, mean PC1 +30.2, PC2 +26.2, PC3 -0.0, PC4 -0.1 JPT: n = 47, mean PC1 +30.3, PC2 +27.1, PC3 -0.2, PC4 +0.2 5-NN population accuracy from the first 2 PCs (5-fold CV): 0.831 5-NN population accuracy from the first 4 PCs (5-fold CV): 0.885 5-NN population accuracy from the first 10 PCs (5-fold CV): 0.860 PCA of the 94 East Asian individuals alone: sign of PC1 separates HCB from JPT for 96.8% of them
PC 1 (12.4% of the variance) separates the Yoruba from everyone else, and PC 2 (5.8%) Europeans from East Asians: the oldest split, Africa against the rest, comes first. Later components explain about 1% each. Han Chinese and Japanese have almost equal means on the first four, so a nearest-neighbour classifier on them reaches only 88.5% (86.0% with 10). Yet a PCA of the 94 East Asians alone separates them along its first component for 96.8% of people. Variance is not importance.
A genome-wide association study (GWAS) tests hundreds of thousands of SNPs against a trait. If the sample mixes populations, a trait that differs between them for non-genetic reasons (diet, healthcare, measurement) is associated with every SNP whose frequency differs. Ancestry causes both: population stratification, a textbook confounder.
The standard remedy (Price et al., 2006, EIGENSTRAT) adds the top genotype PCs as covariates. They estimate the unobserved confounder, and adjusting for them blocks the backdoor path through ancestry. It works because ancestry leaves a strong low-rank signature; it can fail when confounding varies on a finer scale, and modern studies add mixed models with a genetic-relatedness matrix.
A matrix has singular values 5, 3 and 1. What is the smallest possible squared Frobenius error \(\lVert A-B\rVert_F^2\) for a matrix \(B\) of rank 1?
PCA is a procedure, not a model: it gives no probability for a new point, no principled treatment of missing values and no likelihood for comparing dimensions. Probabilistic PCA (Tipping and Bishop, 1999; Roweis, 1998) writes the data as a few latent (hidden) factors seen through fixed weights, the loadings, plus noise; test scores might be explained by two latent abilities, verbal and numerical.
Both models generate \(x\in\mathbb R^d\) from a latent vector \(z\in\mathbb R^k\) through a \(d\times k\) loading matrix \(W\):
$$z\sim N(0,I_k),\qquad x=Wz+\mu+\varepsilon.$$Marginally, the covariance is low rank plus a simple term:
$$x\sim N(\mu,\,WW^\top+\sigma^2I)\qquad\text{or}\qquad x\sim N(\mu,\,WW^\top+\Psi).$$Let \(S\) have eigenvalues \(\lambda_1\ge\dots\ge\lambda_d\) and eigenvectors \(U=(v_1,\dots,v_d)\). The maximum-likelihood estimates of probabilistic PCA with \(k\) factors are \(\hat\mu=\bar x\) and
$$\hat\sigma^2=\frac1{d-k}\sum_{j>k}\lambda_j,\qquad\hat W=U_k\big(\Lambda_k-\hat\sigma^2I\big)^{1/2}R,$$So the columns of \(\hat W\) span the PCA subspace, and the noise variance is the average variance in the discarded directions.
(Statement only; the proof sets the derivative of the log-likelihood to zero and analyses its stationary points.)
The likelihood depends on \(W\) only through \(WW^\top\), so factors are identified only up to rotation. (Psychologists, who invented factor analysis to find "general intelligence", spent decades on rotations that make factors nameable.) A likelihood also lets us choose \(k\) on held-out data, as in Lecture 14.
# Probabilistic PCA: closed-form maximum likelihood, held-out likelihood to choose k; factor analysis from sklearn.decomposition import PCA, FactorAnalysis person = np.repeat(np.arange(40), 10) # 10 images of each of 40 people tr_i, te_i = person < 30, person >= 30 # hold out 10 people entirely for k in [5, 20, 50, 100, 200, 250, 290]: pp = PCA(k).fit(X[tr_i]) # PCA.score = average log-likelihood under PPCA s2 = pp.noise_variance_ print(f"PPCA k = {k:3d}: sigma^2 = mean discarded eigenvalue = {s2:.5f}; held-out log-likelihood per face {pp.score(X[te_i]):8.1f}") # factor analysis vs PCA when the noise is uneven across variables rng = np.random.default_rng(4); n2 = 2000 Wtrue = rng.normal(size=(10, 2)); Zf = rng.normal(size=(n2, 2)) psi = np.full(10, 0.2); psi[0] = 25.0 # variable 0 is very noisy Y = Zf @ Wtrue.T + rng.normal(size=(n2, 10)) * np.sqrt(psi) def angle(A, B): # largest principal angle between column spaces (degrees) qa, qb = np.linalg.qr(A)[0], np.linalg.qr(B)[0] return np.degrees(np.arccos(np.clip(np.linalg.svd(qa.T @ qb)[1].min(), -1, 1))) pc = PCA(2).fit(Y); fa = FactorAnalysis(2, random_state=0).fit(Y) print(f"uneven noise (variance 25 on one variable, 0.2 on the others): angle to the true 2-D loading space") print(f" PCA {angle(pc.components_.T, Wtrue):5.1f} degrees; factor analysis {angle(fa.components_.T, Wtrue):5.1f} degrees; " f"FA's estimated noise variances: {fa.noise_variance_[0]:.1f} (variable 0), median of the rest {np.median(fa.noise_variance_[1:]):.2f}")
PPCA k = 5: sigma^2 = mean discarded eigenvalue = 0.18785; held-out log-likelihood per face -545.9 PPCA k = 20: sigma^2 = mean discarded eigenvalue = 0.09872; held-out log-likelihood per face 691.4 PPCA k = 50: sigma^2 = mean discarded eigenvalue = 0.05617; held-out log-likelihood per face 1725.4 PPCA k = 100: sigma^2 = mean discarded eigenvalue = 0.03280; held-out log-likelihood per face 2641.0 PPCA k = 200: sigma^2 = mean discarded eigenvalue = 0.01477; held-out log-likelihood per face 3806.9 PPCA k = 250: sigma^2 = mean discarded eigenvalue = 0.00952; held-out log-likelihood per face 4287.8 PPCA k = 290: sigma^2 = mean discarded eigenvalue = 0.00505; held-out log-likelihood per face 4624.1 uneven noise (variance 25 on one variable, 0.2 on the others): angle to the true 2-D loading space PCA 76.0 degrees; factor analysis 1.2 degrees; FA's estimated noise variances: 25.2 (variable 0), median of the rest 0.20
The fitted noise variance is the mean discarded eigenvalue, falling from 0.188 with 5 factors to 0.005 with 290. On ten held-out people the log-likelihood per face rises all the way to 290 factors, near the maximum 300 training faces allow: face variance decays smoothly over hundreds of directions, not "a few factors plus isotropic noise". A probabilistic model judges dimension only as well as its noise assumption.
With two true factors in ten variables, one carrying 125 times the noise of the others, PCA's first two components are 76.0° from the true loading space: most of the variance is the noisy variable. Factor analysis estimates the noise variances correctly (25.2 and 0.20) and recovers the space to within 1.2°. Use it when variables differ in precision; standardise before PCA when they differ in scale.
Bayes' rule gives the posterior of the latent factors for each point:
$$p(z\mid x)=N\big(M^{-1}W^\top(x-\mu),\;\sigma^2M^{-1}\big),\qquad M=W^\top W+\sigma^2I.$$This shrinks the scores towards zero in poorly determined directions. The model fills in missing values by conditional expectation, can be fitted by the EM algorithm of Lecture 17a without forming the \(d\times d\) covariance, and extends to mixtures of PCAs for data that are locally but not globally flat. A prior on \(W\) gives Bayesian PCA (Bishop, 1999), whose automatic relevance determination chooses \(k\) by the evidence. With a neural network as the map from \(z\) to \(x\), the same structure is the variational autoencoder of Lecture 16b.
PCA needs an SVD, about \(nd\min(n,d)\) operations. A cruder idea ignores the data: multiply every point by one random \(d\times k\) matrix. A random subspace keeps almost none of the faces' variance (Section 2), yet it keeps all pairwise distances up to a small factor, in a dimension depending only on the number of points.
The reason is concentration (Lecture 14). Each of the \(k\) random weighted sums is a noisy reading of a vector's length, but the average of \(k\) squared readings has relative error about \(1/\sqrt k\). The chance that any of the \(n^2/2\) pairs is badly distorted falls exponentially in \(k\), so \(k\) need grow only like \(\log n\).
Let \(0<\varepsilon<1\), let \(x_1,\dots,x_n\in\mathbb R^d\), and let
$$k\;\ge\;\frac{4\ln n}{\varepsilon^2/2-\varepsilon^3/3}.$$Let \(R\) be a \(k\times d\) matrix of independent \(N(0,1/k)\) entries and \(f(x)=Rx\). Then with probability at least \(1/n\), for all pairs \(i,j\),
$$(1-\varepsilon)\lVert x_i-x_j\rVert^2\le\lVert f(x_i)-f(x_j)\rVert^2\le(1+\varepsilon)\lVert x_i-x_j\rVert^2.$$In particular such a map exists, and repeating the random draw \(O(n)\) times finds one with high probability.
One vector. Fix \(u=x_i-x_j\ne0\). Each coordinate of \(Ru\) is \(N(0,\lVert u\rVert^2/k)\), and the coordinates are independent. So
$$Q=\frac{k\lVert Ru\rVert^2}{\lVert u\rVert^2}\sim\chi^2_k,\qquad\mathbb Ee^{tQ}=(1-2t)^{-k/2}\quad(t<1/2).$$Upper tail. By Markov's inequality applied to \(e^{tQ}\), for \(0<t<1/2\),
$$P\big(Q\ge(1+\varepsilon)k\big)\le(1-2t)^{-k/2}e^{-t(1+\varepsilon)k}.$$The choice \(t=\frac{\varepsilon}{2(1+\varepsilon)}\) gives the bound \(\big((1+\varepsilon)e^{-\varepsilon}\big)^{k/2}\). Since \(\ln(1+\varepsilon)\le\varepsilon-\varepsilon^2/2+\varepsilon^3/3\), this is at most
$$\exp\!\big(-\tfrac k2(\varepsilon^2/2-\varepsilon^3/3)\big).$$Lower tail. The same argument with \(e^{-tQ}\) and \(t=\frac{\varepsilon}{2(1-\varepsilon)}\), using \(\ln(1-\varepsilon)\le-\varepsilon-\varepsilon^2/2\), gives
$$P\big(Q\le(1-\varepsilon)k\big)\le\big((1-\varepsilon)e^{\varepsilon}\big)^{k/2}\le e^{-k\varepsilon^2/4},$$which is smaller than the upper-tail bound.
All pairs. With \(k\) as stated, the upper-tail bound is at most \(e^{-2\ln n}=n^{-2}\), so each pair fails with probability at most \(2/n^2\).
By the union bound over the \(n(n-1)/2\) pairs, some pair fails with probability at most \((n-1)/n=1-1/n\). \(\square\)
The bound does not involve \(d\). A million points can be embedded in about
$$\frac{4\ln(10^6)}{0.02-0.0027}\approx3{,}200$$dimensions with every squared distance within 20%, whether they started in ten thousand dimensions or ten billion; a thousand times more points need only about 50% more. The worst-case bound is conservative: far fewer dimensions preserve most distances in practice.
# Random projections: Johnson-Lindenstrauss in practice on the 4,096-pixel faces from scipy.spatial.distance import pdist D0 = pdist(X, 'sqeuclidean') # 79,800 squared distances rng = np.random.default_rng(5) print(" k random projection: ratio of squared distances PCA to k dims JL bound on k for") print(" min 1% 99% max share within 20% min max eps = 0.2, n = 400") for k in [10, 50, 200, 399]: R = rng.normal(size=(d, k)) / np.sqrt(k) # entries N(0, 1/k) (PCA can use at most 399 dims here) r = pdist(X @ R, 'sqeuclidean') / D0 rp = pdist(Xc @ Vt[:k].T, 'sqeuclidean') / D0 kb = 4 * np.log(400) / (0.2**2 / 2 - 0.2**3 / 3) print(f"{k:4d} {r.min():.3f} {np.quantile(r, .01):.3f} {np.quantile(r, .99):.3f} {r.max():.3f} {np.mean(abs(r - 1) < 0.2):6.1%}" f" {rp.min():.3f} {rp.max():.3f} {kb:.0f}")
k random projection: ratio of squared distances PCA to k dims JL bound on k for
min 1% 99% max share within 20% min max eps = 0.2, n = 400
10 0.062 0.263 2.149 3.690 35.5% 0.021 0.934 1383
50 0.502 0.679 1.502 1.893 73.7% 0.141 0.977 1383
200 0.643 0.812 1.239 1.466 96.7% 0.378 0.997 1383
399 0.746 0.877 1.190 1.319 99.3% 1.000 1.000 1383
For the 400 faces and \(\varepsilon=0.2\) the guarantee needs \(k\ge1383\), a third of the 4,096 dimensions. In practice 200 random dimensions keep 96.7% of the 79,800 squared distances within 20% (worst pair: factor 1.466); 10 are hopeless (ratios from 0.06 to 3.7).
PCA's ratios never exceed 1, since orthogonal projection only shrinks distances, and with 50 components some pairs keep only 14%: two photos of one person differing in fine detail look almost identical. PCA keeps total variance best by sacrificing small distances; random projections treat all pairs alike. Hence their use in nearest-neighbour search, sketching, and randomised linear algebra, where a random projection shrinks a matrix before an exact SVD gives an accurate approximate PCA (Halko, Martinsson and Tropp, 2011).
You need to embed 10,000 points with all squared distances preserved to within 10%, using the bound of Theorem 16.4. The points currently have 50 dimensions. What should you conclude?
A ratings matrix has a row per user, a column per item, and entries almost nowhere; predicting the missing ones is the recommendation problem. Describe each user and item by \(k\) hidden numbers ("how much this user likes action", "how much action this film has") and model a rating as their inner product. A few tastes (action over romance, acclaim over spectacle) explain much of how people rate, so the matrix is roughly low rank.
Given observed ratings \(r_{ui}\) for pairs \((u,i)\) in a set \(\Omega\), fit a global mean \(\mu\), biases \(b_u,b_i\) and factor vectors \(p_u,q_i\in\mathbb R^k\) by minimising
$$\sum_{(u,i)\in\Omega}\big(r_{ui}-\mu-b_u-b_i-p_u^\top q_i\big)^2+\lambda\Big(\sum_ub_u^2+\sum_ib_i^2+\sum_u\lVert p_u\rVert^2+\sum_i\lVert q_i\rVert^2\Big).$$Only observed entries enter the loss, unlike an SVD of a filled-in matrix.
Alternating least squares fixes the item parameters and solves a small ridge regression (Lecture 3) for each user, then the reverse, and repeats.
Each half-step is convex with a closed form, so, as in Lloyd's algorithm (Lecture 15), the objective never increases; the whole problem is not convex, since \(p_u^\top q_i\) is a product of unknowns. The penalty is essential: a user with three ratings has \(k+1\) parameters, which would otherwise fit them exactly.
100,000 ratings (1 to 5 stars) of 1,682 films by 943 MovieLens users, each with at least 20 ratings, collected by GroupLens at the University of Minnesota between September 1997 and April 1998 (Harper and Konstan, 2015). We use the standard split u1.base/u1.test (80,000 training, 20,000 test ratings) from the copy of the official archive in the GitHub repository rudrasingh21/Data-ML-100k-, as GroupLens's server was not reachable. Research use is permitted under GroupLens's terms.
# Matrix factorisation on MovieLens 100K: predict held-out ratings from 943 users x 1,682 films import pandas as pd cols = ['user', 'item', 'rating', 'ts'] trn = pd.read_csv('data/ml-100k/u1.base', sep='\t', names=cols); tst = pd.read_csv('data/ml-100k/u1.test', sep='\t', names=cols) titles = pd.read_csv('data/ml-100k/u.item', sep='|', header=None, encoding='latin-1')[1].to_numpy() nu, ni = 943, 1682; u, i, r = trn.user.values - 1, trn.item.values - 1, trn.rating.values.astype(float) ut, it, rt = tst.user.values - 1, tst.item.values - 1, tst.rating.values.astype(float) rmse = lambda pred: np.sqrt(np.mean((pred - rt)**2)) print(f"{len(trn):,} training and {len(tst):,} test ratings; {len(trn) / (nu * ni):.1%} of the matrix is observed") g = r.mean(); print(f"predict the global mean {g:.2f}: test RMSE {rmse(np.full(len(rt), g)):.4f}") def als(k, reg, iters=15, seed=0): # alternating least squares with user and item biases rg = np.random.default_rng(seed); P = 0.1 * rg.normal(size=(nu, k)); Q = 0.1 * rg.normal(size=(ni, k)) bu = np.zeros(nu); bi = np.zeros(ni) byu = [np.flatnonzero(u == a) for a in range(nu)]; byi = [np.flatnonzero(i == b) for b in range(ni)] for _ in range(iters): for a in range(nu): # solve for user a's bias and factors, items fixed ix = byu[a]; A = np.c_[np.ones(len(ix)), Q[i[ix]]] sol = np.linalg.solve(A.T @ A + reg * np.eye(k + 1), A.T @ (r[ix] - g - bi[i[ix]])); bu[a], P[a] = sol[0], sol[1:] for b in range(ni): ix = byi[b] if len(ix) == 0: continue A = np.c_[np.ones(len(ix)), P[u[ix]]] sol = np.linalg.solve(A.T @ A + reg * np.eye(k + 1), A.T @ (r[ix] - g - bu[u[ix]])); bi[b], Q[b] = sol[0], sol[1:] return bu, bi, P, Q pred = lambda m: np.clip(g + m[0][ut] + m[1][it] + np.sum(m[2][ut] * m[3][it], 1), 1, 5) m0 = als(0, 10.0, iters=5); print(f"user and item biases only: test RMSE {rmse(pred(m0)):.4f}") for k, reg in [(2, 10.0), (10, 10.0), (50, 10.0), (50, 1.0), (50, 30.0)]: print(f"biases + rank {k:2d} factors, lambda = {reg:4.1f}: test RMSE {rmse(pred(als(k, reg))):.4f}") M2 = als(2, 10.0); cnt_i = np.bincount(i, minlength=ni) pop_i = np.flatnonzero(cnt_i >= 100) for f in range(2): o = pop_i[np.argsort(M2[3][pop_i, f])] print(f"factor {f + 1}, low end: {'; '.join(titles[o[:3]])}\n high end: {'; '.join(titles[o[-3:]])}")
80,000 training and 20,000 test ratings; 5.0% of the matrix is observed
predict the global mean 3.53: test RMSE 1.1537
user and item biases only: test RMSE 0.9598
biases + rank 2 factors, lambda = 10.0: test RMSE 0.9305
biases + rank 10 factors, lambda = 10.0: test RMSE 0.9253
biases + rank 50 factors, lambda = 10.0: test RMSE 0.9328
biases + rank 50 factors, lambda = 1.0: test RMSE 1.1688
biases + rank 50 factors, lambda = 30.0: test RMSE 0.9682
factor 1, low end: Star Wars (1977); Return of the Jedi (1983); Terminator, The (1984)
high end: Postino, Il (1994); Evita (1996); English Patient, The (1996)
factor 2, low end: Leaving Las Vegas (1995); Dead Man Walking (1995); Boogie Nights (1997)
high end: Saint, The (1997); Twister (1996); Independence Day (ID4) (1996)
Only 5.0% of the matrix is observed. The global mean (3.53 stars) gives test RMSE 1.1537; user and item biases bring it to 0.9598, most of the gain. Two factors give 0.9305 and ten 0.9253; fifty are slightly worse (0.9328), and the penalty matters (\(\lambda=1\): 1.1688, worse than biases alone; \(\lambda=30\): 0.9682).
The first factor runs from Star Wars, Return of the Jedi and The Terminator to Il Postino, Evita and The English Patient (blockbusters against prestige dramas); the second sets Leaving Las Vegas, Dead Man Walking and Boogie Nights against The Saint, Twister and Independence Day (admired films against mainstream entertainment). Nobody told the model what genres are.
How many parameters does the model of Definition 16.3 have for MovieLens 100K with \(k=10\)? (Count the global mean, the biases and the factors.)
In October 2006 Netflix offered US$1 million for beating its recommender, Cinematch, by 10% in RMSE, releasing 100 million ratings by 480,000 customers of 17,770 films. Simon Funk's blog post "Netflix Update: Try This at Home" (December 2006) described regularised matrix factorisation by stochastic gradient descent and took him near the top within weeks; biases, implicit feedback and time effects followed (Koren, Bell and Volinsky, 2009). BellKor's Pragmatic Chaos won in September 2009 with a blend of hundreds of models, submitted 20 minutes before an equally accurate rival. Netflix never deployed the full blend, judging it not worth the engineering cost, and cancelled a second prize in 2010 after the "anonymised" ratings were linked to public IMDb reviews (Narayanan and Shmatikov, 2008) and a privacy lawsuit followed.
Lloyd, Mohseni and Rebentrost (2014) showed that a quantum computer given many copies of a density matrix \(\rho\) can reveal its leading eigenvectors in time polylogarithmic in the dimension. Kerenidis and Prakash (2017) built on this a quantum recommendation algorithm, apparently exponentially faster than any classical method.
In 2018 Ewin Tang, an 18-year-old undergraduate at the University of Texas at Austin working with Scott Aaronson, found a classical algorithm with the same polylogarithmic dependence given the same input access: sampling rows and entries with probability proportional to their squared norms (Tang, STOC 2019). The speed-up came from the input model, not quantum mechanics. "Dequantisation" has since reached quantum PCA and other proposals. The classical versions still have large polynomial overheads, so how much quantum advantage survives is still being studied.
word2vec implicitly factorises a word co-occurrence matrix (Levy and Goldberg, 2014), and latent semantic analysis (Lecture 12) is an SVD of a term–document matrix. LoRA (Hu et al., 2021) fine-tunes large language models by learning a low-rank update \(\Delta W=BA\) for each frozen weight matrix, often of rank 8 or 16 for matrices with thousands of rows. Vector databases compress embeddings by PCA before indexing. These, compressed sensing, the Gaussian-process approximations of Lecture 7, and genetic PCA covariates rest on one observation: real data matrices have quickly decaying singular values.
The sample covariance of the two scores is
$$\frac1{n-1}\sum_iv_1^\top(x_i-\bar x)(x_i-\bar x)^\top v_2=v_1^\top Sv_2=\lambda_2v_1^\top v_2=0.$$In general the score vectors are the columns of \(U\Sigma\), which are orthogonal: PCA rotates the data so that the new coordinates are uncorrelated.
Variance depends on units. Unstandardised, waiting time has about \((13.6/1.14)^2\approx142\) times the variance of duration, so the first component is essentially the waiting-time axis, whatever the correlation.
After standardising, the first component lies along the strong positive correlation, as in the widget of Section 1. Standardising is a choice too: it treats every variable as equally important.
The rows of \(X_c\) sum to zero, so its rank is at most \(n-1\), and \(S=X_c^\top X_c/(n-1)\) has the same rank. With one point, \(X_c=0\).
For the faces, \(n=400\le d=4096\), so at most 399 eigenvalues are non-zero, as the code found; the other 3,697 directions carry no variance in the sample, and PCA can say nothing about them.
With this \(t\), \(1-2t=1-\varepsilon/(1+\varepsilon)=1/(1+\varepsilon)\), so
$$(1-2t)^{-k/2}=(1+\varepsilon)^{k/2}.$$Also \(t(1+\varepsilon)k=\varepsilon k/2\), so \(e^{-t(1+\varepsilon)k}=e^{-\varepsilon k/2}\). The product is \(\big((1+\varepsilon)e^{-\varepsilon}\big)^{k/2}\). (This \(t\) minimises the bound over \(t\).)
As \(\lambda\to0\), \(k+1\) parameters face one equation, so infinitely many fit exactly; ALS picks one arbitrarily and predictions for the user's other films are meaningless (the overfitting seen at \(\lambda=1\)).
As \(\lambda\to\infty\), bias and factors shrink to zero and predictions become \(\mu+b_i\), the item's average appeal.
The best \(\lambda\) lies between and is chosen on held-out ratings (\(\lambda=10\) beat 1 and 30).
Replace Gs by the centred genotypes without dividing. The main picture (Africa, Europe, East Asia) is unchanged, because it is carried by thousands of SNPs.
Without standardisation, SNPs with intermediate frequencies (\(p\) near 0.5, where \(2p(1-p)\) is largest) weigh more and rare variants less. Patterson et al.'s scaling gives each SNP equal weight, assuming independent drift, which emphasises rarer variants that often differ more sharply between populations.
Each project uses this lecture's methods and public data, and has a clear result.
Data. Olivetti faces: AT&T Laboratories Cambridge, 64×64 version distributed with scikit-learn, PNG copy from github.com/lloydmeta/Olivetti-PNG. HapMap Phase II genotypes (279 individuals, 9,088 SNPs): sample shipped with SNPRelate, github.com/zhengxwen/SNPRelate (GPL-3), extracted by data/hapmap_from_gds.py; used in place of the 1000 Genomes Project, which could not be downloaded. MovieLens 100K: GroupLens, University of Minnesota, copy from github.com/rudrasingh21/Data-ML-100k-. Old Faithful: R datasets::faithful, as in Lecture 14.
continued in Lecture 16b: nonlinear methods | numbers in the text not printed by a code box are computed in verify_L16a.py, figures and widget data in figs_L16a.py; code-box outputs are pasted from actual runs (numpy, SciPy and scikit-learn on one CPU core)