Dimensionality Reduction Overview

Chapter 9 fitted a function to labelled data. Chapter 10 has no labels — only $\mathbf{x}$, and the second of the book’s four pillars: “dimensionality reduction exploits structure and correlation and allows us to work with a more compact representation of the data, ideally without losing information.”

PCA is over a hundred years old, and the chapter derives it twice.

One answer, two derivations

	§10.2 maximum variance	§10.3 projection
what you maximise or minimise	the variance you keep	the error you pay
the objective	$\mathrm{tr}(\mathbf{B}\mathbf{B}^\top\mathbf{S})$	$\mathrm{tr}(\mathbf{B}_\perp\mathbf{B}_\perp^\top\mathbf{S})$
at the optimum	$\sum_{m\le M}\lambda_m$	$\sum_{j>M}\lambda_j$
the answer	the top $M$ eigenvectors	the top $M$ eigenvectors

They are not two methods that happen to agree. $V_M + J_M = \mathrm{tr}(\mathbf{S})$ for every $M$ and every orthonormal $\mathbf{B}$ — measured constant to $2.3\times10^{-13}$ against a trace of $741.158872$. One quantity, read from either end of a fixed total. That is why the book can write “we omit a derivation that is identical to the one presented in Section 10.2” and lose nothing.

Where the measuring pays off

Everything in this chapter has a closed form, so every claim can be checked exactly. Five that turned up something:

The four words “with mean $\mathbf{0}$” carry Equation 10.1. Applied to raw data it is the second-moment matrix, not the covariance. Measured on $174$ images of the digit “8”: the trace inflates by $5.4245$ and the leading direction swings $87.9996^\circ$ — landing $0.2851^\circ$ from the mean image, a direction on which every data point has nearly the same coordinate.

§10.5 contains an off-by-one that centred data contradicts. The book says the Gram matrix “has rank $N$ and is invertible”. For the centred data it assumes in its own first sentence, the rank is $N-1$ and the condition number is $4.15\times10^{17}$ — the all-ones vector sits in the null space. The adjacent claim of $D-N+1$ zero eigenvalues is the correct one.

Held-out reconstruction error cannot choose $M$. Chapter 9’s test RMSE rose past the right degree, which is what made it usable. This one falls monotonically to zero, because a larger subspace can never project a point further away — on any data. Four defensible rules applied to the same spectrum give $M = 1$, $18$, $25$ and $38$.

Equation 10.32 is not a general formula for coordinates. It is what Equation 10.34’s $(\mathbf{B}^\top\mathbf{B})^{-1}$ collapses to when the columns are orthonormal. Applied to a basis spanning the identical subspace but rescaled, the reconstruction error goes from $16.316272$ to $24.728409$, with nothing raised.

Standardising is a modelling decision, not tidiness. Changing height from metres to millimetres rotates the leading direction $77.3982^\circ$ on data that never moved. After Step 2 the three unit choices agree to $1.2\times10^{-6}$ degrees — and the standardised covariance is the correlation matrix, with trace exactly $D$.

The pages

#	page	book section	the measured claim
1001	Problem Setting	§10.1	skip the centring and $\mathbf{b}_1$ moves $87.9996^\circ$
1002	The Maximum Variance Perspective	§10.2	$V_1 = \lambda_1$ to $8.5\times10^{-14}$; random search reaches $37.18\%$
1003	The Projection Perspective	§10.3.1–10.3.2	the residual is $100\%$ in $U^\perp$, to twelve decimals
1004	Finding the Principal Subspace	§10.3.3	$200{,}000$ random bases, zero beat the eigenbasis
1005	Eigenvector Computation and Low-Rank Approximations	§10.4	eigh returns $18$ negative eigenvalues at $\kappa = 10^{10}$
1006	PCA in High Dimensions	§10.5	$4565\times$ faster at $D = 4000$, and the book is off by one
1007	Key Steps of PCA in Practice	§10.6	a unit change costs $77.3982^\circ$; the leak makes it look better
1008	The Latent Variable Perspective	§10.7	$\mathbf{C} = \sigma^2\boldsymbol\Lambda^{-1}$, and it never sees the data
1009	Chapter 10 Worked Problems	—	eight problems, this module’s own
1010	Chapter 10 Formula Sheet	—	every equation and every measured constant

Chapter 10 has no end-of-chapter exercises

Like Chapters 8 and 9, it runs straight from §10.8 into Chapter 11. Page 1009’s problems are this module’s own, built from claims the chapter makes, and should not be attributed to Deisenroth, Faisal and Ong.

About the dataset

The book’s running example is MNIST — $60{,}000$ digits at $28\times28$, so $\mathbf{x}\in\mathbb{R}^{784}$. These pages use the $8\times8$ version of the same UCI corpus that ships inside scikit-learn, so every number reproduces with no download: $N = 174$ images of the digit “8”, $D = 64$. The structure is identical and the figures are smaller; where the difference matters — the spectrum is flatter at $D=64$ than at $D=784$ — the pages say so.

The thread that runs through it

One number appears on four pages by four routes, and noticing that is most of understanding the chapter:

where it appears	page	value
$\sum_{j>5}\lambda_j$, Equation 10.44	1002	$320.123369$
the measured reconstruction error, Equation 10.29	1002	$320.123369$
$\mathrm{tr}(\mathbf{B}_\perp\mathbf{B}_\perp^\top\mathbf{S})$, Equation 10.43b	1004	$320.123369$
$\lVert\mathbf{X}-\tilde{\mathbf{X}}_5\rVert_F^2/N$, Eckart–Young	1005	$320.123369$

It is $J_5$, the price of a five-number code. §10.2 reached it without ever forming a projection, §10.3 by deriving it, §10.4 as a theorem about matrix approximation. Three literatures, one number.

What only the probabilistic view can do

§10.7 puts a generative model behind all of it — the same move §9.3 made for regression — and the payoff is measurable rather than rhetorical:

capability	measured
fill in pixels never observed	$36.8\%$ better than mean-filling at $10\%$ missing
score novelty	every digit “0” above the $8$s’ $95$th percentile
a posterior whose width you know in advance	$\mathbf{C} = \sigma^2\boldsymbol\Lambda^{-1}$, unchanged across $200$ observations
estimate the noise you are discarding	$\sigma^2_{\mathrm{ML}} = J_M/(D-M)$, exact to $8$ decimals

And it recovers everything before it: PPCA is PCA with shrinkage, each axis scaled by $(\lambda_m-\sigma^2)/\lambda_m$ — measured to six decimals — converging to PCA as $\sigma\to0$.

What the chapter cannot do, and says so

Two limits are worth carrying forward, because both are load-bearing for later chapters.

PCA finds the subspace, not the signals. The objective depends on $\mathbf{B}\mathbf{B}^\top$ alone, so rotating $\mathbf{B}$ by any orthogonal $\mathbf{R}$ leaves the error at $320.123369$ and the projector identical to $1.1\times10^{-16}$ — while moving the codes by $39.243537$ and destroying their uncorrelatedness ($5.1\times10^{-14}$ becomes $37.046852$). That is Equation 10.78’s arbitrary $\mathbf{R}$, and it is why independent component analysis exists.

PCA is linear, and some data is not. A noisy circle in $\mathbb{R}^2$ has one intrinsic degree of freedom and two nearly equal eigenvalues, $0.501038$ and $0.497606$; no line keeps more than $50.17\%$. But §10.5’s $N\times N$ matrix is built entirely from inner products, and $D$ appears nowhere in it — so swapping the Gram matrix for a kernel matrix takes one line and separates two concentric rings from $0.0597$ to $7.5299$. Kernel PCA is this chapter with one substitution, and Chapter 12 makes the same one.

Where it goes next

§10.8’s pointer	and where it already appeared
kernel PCA — infinite-dimensional features	page 1006 measured that $D$ never enters the $N\times N$ matrix; page 1009 ran it
deep auto-encoders — PCA is the identity-activation case	Equation 10.76, and page 1004’s rotation ambiguity
factor analysis — a different $\sigma^2_d$ per dimension	page 1007’s $12$ zero-variance pixels are the degenerate case
ICA — a non-Gaussian prior on $\mathbf{z}$	page 1004’s $\mathbf{R}$, measured to leave $J_M$ exactly unchanged
Bayesian PCA — integrate the parameters out	Chapter 9’s §9.3, and page 908’s marginal likelihood

And the remaining pillars: Chapter 11 applies the same machinery to density estimation, Chapter 12 to classification.

Recall card

• Chapter 10 has no labels. The data is just x, and the task is a compact representation of it that loses as little as possible.
• The chapter derives PCA twice — by maximising the variance kept and by minimising the reconstruction error — and reaches the same eigenvectors both times.
• That is not a coincidence: the variance kept and the error paid always sum to the trace of the covariance matrix, measured constant to 2.3e-13.
• Equation 10.1 is a covariance only because the data is assumed centred. Skip that and the leading direction swings 87.9996 degrees onto the mean image itself.
• One number, 320.123369, appears by four independent routes — the leftover eigenvalues, the measured error, a trace, and the Eckart-Young theorem.
• Two hundred thousand random orthonormal bases, and not one beats the eigenbasis.
• The objective sees only the projection matrix, so rotating the basis changes the codes by 39.243537 and the error by nothing. PCA finds the subspace, not the signals.
• Held-out reconstruction error cannot choose the code length, because it falls monotonically to zero. Four defensible rules give four different answers.
• Use the SVD of the data, not the eigendecomposition of the covariance, whenever the small eigenvalues matter — squaring the condition number returns 18 negative eigenvalues at 1e10.
• When there are fewer points than dimensions, decompose the N-by-N Gram matrix instead — 4565 times faster at D equal to 4000.
• And that matrix is built from inner products with no D in it, which is the whole of kernel PCA.
• Standardising is a decision: a change of unit costs 77.3982 degrees without it, and it throws away real information with it.
• Probabilistic PCA adds a generative story, which buys imputation, novelty scoring and a posterior covariance known before any data arrives — and recovers plain PCA as the noise-free limit.

Start here: Problem Setting