Chapter 10 Formula Sheet

One page for the whole chapter. Equation numbers are the book’s; the measured columns are this module’s, computed on $174$ images of the digit “8” at $D = 64$ unless stated otherwise.

The chapter in one table

Two derivations, one answer.

	§10.2 maximum variance	§10.3 minimum reconstruction error	§10.7 probabilistic PCA
what is optimised	$V_M$, the variance kept	$J_M$, the error paid	a likelihood
the objective	$\mathrm{tr}(\mathbf{B}\mathbf{B}^\top\mathbf{S})$	$\mathrm{tr}(\mathbf{B}_\perp\mathbf{B}_\perp^\top\mathbf{S})$	$p(\mathbf{x}) = \mathcal{N}(\boldsymbol\mu, \mathbf{B}\mathbf{B}^\top+\sigma^2\mathbf{I})$
at the optimum	$\sum_{m\le M}\lambda_m$	$\sum_{j>M}\lambda_j$	$\sigma^2_{\mathrm{ML}} = \frac{1}{D-M}\sum_{j>M}\lambda_j$
the answer	top $M$ eigenvectors	top $M$ eigenvectors	the same subspace, shrunk
the two sum to	$\mathrm{tr}(\mathbf{S}) = 741.158872$, measured constant to $2.3\times10^{-13}$

§10.1 Problem setting

what	equation
data covariance matrix	$\mathbf{S} = \frac1N\sum_n\mathbf{x}_n\mathbf{x}_n^\top$ — 10.1, mean $\mathbf{0}$ assumed
the code	$\mathbf{z}_n = \mathbf{B}^\top\mathbf{x}_n \in \mathbb{R}^M$ — 10.2
the projection matrix	$\mathbf{B} = [\mathbf{b}_1,\ldots,\mathbf{b}_M] \in \mathbb{R}^{D\times M}$, orthonormal columns — 10.3
the reconstruction	$\tilde{\mathbf{x}} = \mathbf{B}\mathbf{B}^\top\mathbf{x} \in \mathbb{R}^D$
the layout	$\mathbf{X} \in \mathbb{R}^{D\times N}$ — data points are the columns

Equation 10.1 is a covariance only if the mean is zero

Applied to raw data it exceeds the covariance by $\boldsymbol\mu\boldsymbol\mu^\top$ — measured to $5.7\times10^{-14}$. On the digit-”8” images that inflates the trace from $741.158872$ to $4020.390805$, a factor of $5.4245$, and swings the leading direction $87.9996^\circ$ onto the mean image ($0.2851^\circ$ from it).

§10.2 Maximum variance perspective

what	equation
variance of the first coordinate	$V_1 = \frac1N\sum_n z_{1n}^2$, $z_{1n} = \mathbf{b}_1^\top\mathbf{x}_n$ — 10.7, 10.8
in matrix form	$V_1 = \mathbf{b}_1^\top\mathbf{S}\mathbf{b}_1$ — 10.9b
the constrained problem	$\max\ \mathbf{b}_1^\top\mathbf{S}\mathbf{b}_1$ s.t. $\lVert\mathbf{b}_1\rVert^2 = 1$ — 10.10
the Lagrangian	$\mathfrak{L} = \mathbf{b}_1^\top\mathbf{S}\mathbf{b}_1 + \lambda_1(1-\mathbf{b}_1^\top\mathbf{b}_1)$ — 10.11
stationarity	$\mathbf{S}\mathbf{b}_1 = \lambda_1\mathbf{b}_1$ — 10.13
the variance kept	$V_1 = \lambda_1$ — 10.15
the deflation	$\hat{\mathbf{X}} = \mathbf{X} - \sum_{i<m}\mathbf{b}_i\mathbf{b}_i^\top\mathbf{X}$ — 10.17
shared eigenvectors	$\hat{\mathbf{S}}\mathbf{b}_m = \mathbf{S}\mathbf{b}_m = \lambda_m\mathbf{b}_m$ — 10.21
used-up directions	$\hat{\mathbf{S}}\mathbf{b}_i = \mathbf{0}$ for $i<m$ — 10.22
total kept, total lost	$V_M = \sum_{m\le M}\lambda_m$, $J_M = \sum_{j>M}\lambda_j$ — 10.24, 10.25

The eigendecomposition prices every choice of M at once

$\mathbf{b}_m^\top\mathbf{S}\mathbf{b}_m$ against $\lambda_m$, first six components: largest gap $8.5\times10^{-14}$. No projection has to be formed to know how much variance a component keeps.

Searching for the maximum instead: $200{,}000$ random unit vectors in $\mathbb{R}^{64}$ reach $56.351776$, which is $37.18\%$ of $\lambda_1 = 151.568412$. Power iteration reaches it exactly in $500$ steps.

§10.3 Projection perspective

what	equation
the objective	$J_M = \frac1N\sum_n\lVert\mathbf{x}_n-\tilde{\mathbf{x}}_n\rVert^2$ — 10.29
the reconstruction	$\tilde{\mathbf{x}}_n = \sum_m z_{mn}\mathbf{b}_m = \mathbf{B}\mathbf{z}_n$ — 10.28
the optimal coordinates	$z_{in} = \mathbf{b}_i^\top\mathbf{x}_n$ — 10.32
the general projection	$\tilde{\mathbf{x}} = \mathbf{B}(\mathbf{B}^\top\mathbf{B})^{-1}\mathbf{B}^\top\mathbf{x} = \mathbf{B}\mathbf{B}^\top\mathbf{x}$ — 10.34
the displacement	$\mathbf{x}_n - \tilde{\mathbf{x}}_n = \sum_{j>M}(\mathbf{b}_j^\top\mathbf{x}_n)\mathbf{b}_j$ — 10.38b
the projector	$\sum_{m\le M}\mathbf{b}_m\mathbf{b}_m^\top = \mathbf{B}\mathbf{B}^\top$, symmetric, rank $M$ — 10.39
equivalently	$J_M = \frac1N\sum_n\lVert(\mathbf{I}-\mathbf{B}\mathbf{B}^\top)\mathbf{x}_n\rVert^2$ — 10.40b
as a trace	$J_M = \sum_{j>M}\mathbf{b}_j^\top\mathbf{S}\mathbf{b}_j = \mathrm{tr}\big(\big(\sum_{j>M}\mathbf{b}_j\mathbf{b}_j^\top\big)\mathbf{S}\big)$ — 10.43a, 10.43b
the minimum	$J_M = \sum_{j>M}\lambda_j$ — 10.44
the auto-encoder	$\frac1N\sum_n\lVert\mathbf{x}_n - \mathbf{B}^\top\mathbf{B}\mathbf{x}_n\rVert^2$ — 10.76

Equation 10.32 is what Equation 10.34 collapses to, and not a general formula

The inverse factor is the identity only for orthonormal columns. On five columns spanning the correct subspace but rescaled — $\mathbf{G}^\top\mathbf{G}$ off the identity by $3.84$ — the reconstruction error is $24.728409$ against an available $16.316272$. No error is raised. np.linalg.qr costs nothing and restores the guarantee.

Why Equation 10.32 is a minimum, not just a stationary point

For orthonormal $\mathbf{B}$ and any $\mathbf{z}$:

$$\lVert\mathbf{x}-\mathbf{B}\mathbf{z}\rVert^2 = \lVert\mathbf{x}-\mathbf{B}\mathbf{B}^\top\mathbf{x}\rVert^2 + \lVert\mathbf{B}^\top\mathbf{x}-\mathbf{z}\rVert^2$$

Measured over $200{,}000$ random $\mathbf{z}$ at four scales: worst relative gap $1.7\times10^{-15}$. The first term is what §10.3.3 minimises over bases; the second is the entire cost of not projecting orthogonally.

§10.4 Eigenvector computation

what	equation
the covariance, factored	$\mathbf{S} = \frac1N\mathbf{X}\mathbf{X}^\top$ — 10.45
the SVD	$\mathbf{X} = \mathbf{U}\boldsymbol\Sigma\mathbf{V}^\top$ — 10.47
which gives	$\mathbf{S} = \frac1N\mathbf{U}\boldsymbol\Sigma\boldsymbol\Sigma^\top\mathbf{U}^\top$ — 10.48
the relation	$\lambda_d = \sigma_d^2/N$ — 10.49
the best rank-$M$ approximation	$\tilde{\mathbf{X}}_M = \arg\min_{\mathrm{rk}(\mathbf{A})\le M}\lVert\mathbf{X}-\mathbf{A}\rVert_2$ — 10.50
Eckart–Young	$\tilde{\mathbf{X}}_M = \mathbf{U}_M\boldsymbol\Sigma_M\mathbf{V}_M^\top$ — 10.51
power iteration	$\mathbf{x}_{k+1} = \mathbf{S}\mathbf{x}_k / \lVert\mathbf{S}\mathbf{x}_k\rVert$ — 10.52

Forming X X-transpose squares the condition number

$\kappa(\mathbf{X})$	worst relative error, eigh	worst relative error, SVD	negative eigenvalues
$10^{6}$	$1.1\times10^{-5}$	$2.7\times10^{-11}$	$0$
$10^{8}$	$6.9\times10^{-2}$	$2.8\times10^{-9}$	$0$
$10^{10}$	$\mathbf{5.3\times10^{3}}$	$3.2\times10^{-7}$	$\mathbf{18}$ of $200$

The large eigenvalues are fine either way. The small ones are what Equation 10.44 sums.

§10.5 PCA in high dimensions

what	equation
the eigenvector equation	$\mathbf{S}\mathbf{b}_m = \frac1N\mathbf{X}\mathbf{X}^\top\mathbf{b}_m = \lambda_m\mathbf{b}_m$ — 10.55
the substitution	$\frac1N\mathbf{X}^\top\mathbf{X}\,\mathbf{c}_m = \lambda_m\mathbf{c}_m$, $\mathbf{c}_m := \mathbf{X}^\top\mathbf{b}_m$ — 10.56
the recovery	$\mathbf{S}(\mathbf{X}\mathbf{c}_m) = \lambda_m(\mathbf{X}\mathbf{c}_m)$ — 10.57
the remark	normalise $\mathbf{X}\mathbf{c}_m$ to unit length

measured, $N = 50$ in $D = 784$	value
nonzero eigenvalues	$49$, not $50$ — centring costs one rank
top-$5$ agreement between the two routes	$3.4\times10^{-13}$
the Gram matrix’s condition number	$4.15\times10^{17}$ — singular, contrary to the book
speed-up at $D = 4000$, $N = 50$	$\mathbf{4565.2\times}$
memory, $D = 10{,}000$	$0.745$ GiB against $19.5$ KiB
unnormalised reconstruction error (digits, $M=5$)	$6.269\times10^{4}$ against $1.160\times10^{1}$

§10.6 Key steps in practice

step	equation
1. subtract the mean	—
2. divide by $\sigma_d$	$x_*^{(d)} \leftarrow (x_*^{(d)}-\mu_d)/\sigma_d$ — 10.58
3. eigendecompose $\mathbf{S}$	§10.4
4. project	$\tilde{\mathbf{x}}_* = \mathbf{B}\mathbf{B}^\top\mathbf{x}_*$, $\mathbf{z}_* = \mathbf{B}^\top\mathbf{x}_*$ — 10.59, 10.60
5. undo the standardization	$\tilde{x}_*^{(d)} \leftarrow \tilde{x}_*^{(d)}\sigma_d + \mu_d$ — 10.61
the error as a function of $M$	$\frac1N\sum_n\lVert\mathbf{x}_n-\tilde{\mathbf{x}}_n\rVert^2 = \sum_{i>M}\lambda_i$ — 10.62

Both of the failure modes in Step 2 are silent

Units. Height in metres gives $\mathbf{b}_1 = [0.003887, 0.999992]$; in millimetres, $[0.976750, 0.214380]$ — $77.3982^\circ$ apart, on data that never moved. After Step 2 three unit choices agree to $1.2\times10^{-6}$ degrees, and the standardised covariance is the correlation matrix (measured to $6.7\times10^{-16}$) with trace exactly $D$.

A zero standard deviation. $12$ of the $64$ digit pixels are black in every image, so Equation 10.58 computes $0/0$ — $\mathbf{2{,}088}$ NaNs, no exception.

The wrong statistics. Standardising a test set with its own mean and sd reports $15.400250$ where the honest figure is $15.781992$. The leak makes the model look better.

§10.7 Latent variable perspective

what	equation
the model	$\mathbf{x} = \mathbf{B}\mathbf{z} + \boldsymbol\mu + \boldsymbol\epsilon$, $\boldsymbol\epsilon\sim\mathcal{N}(\mathbf{0},\sigma^2\mathbf{I})$ — 10.63
the generative process	$\mathbf{z}_n\sim\mathcal{N}(\mathbf{0},\mathbf{I})$; $\mathbf{x}_n\mid\mathbf{z}_n\sim\mathcal{N}(\mathbf{B}\mathbf{z}_n+\boldsymbol\mu,\sigma^2\mathbf{I})$ — 10.65, 10.66
the likelihood	$\mathbb{E}[\mathbf{x}] = \boldsymbol\mu$, $\mathbb{V}[\mathbf{x}] = \mathbf{B}\mathbf{B}^\top+\sigma^2\mathbf{I}$ — 10.69, 10.70b
the cross-covariance	$\mathrm{Cov}[\mathbf{x},\mathbf{z}] = \mathbf{B}$ — 10.71
the joint	$\mathcal{N}\!\big([\boldsymbol\mu;\mathbf{0}],\ [\mathbf{B}\mathbf{B}^\top+\sigma^2\mathbf{I},\ \mathbf{B};\ \mathbf{B}^\top,\ \mathbf{I}]\big)$ — 10.72
the posterior mean	$\mathbf{m} = \mathbf{B}^\top(\mathbf{B}\mathbf{B}^\top+\sigma^2\mathbf{I})^{-1}(\mathbf{x}-\boldsymbol\mu)$ — 10.74
the posterior covariance	$\mathbf{C} = \mathbf{I}-\mathbf{B}^\top(\mathbf{B}\mathbf{B}^\top+\sigma^2\mathbf{I})^{-1}\mathbf{B}$ — 10.75, no $\mathbf{x}$ in it
ML parameters	$\boldsymbol\mu_{\mathrm{ML}} = \bar{\mathbf{x}}$; $\mathbf{B}_{\mathrm{ML}} = \mathbf{T}(\boldsymbol\Lambda-\sigma^2\mathbf{I})^{1/2}\mathbf{R}$; $\sigma^2_{\mathrm{ML}} = \frac{1}{D-M}\sum_{j>M}\lambda_j$ — 10.77–10.79

Two closed forms the book does not give

Woodbury on Equation 10.75. $\mathbf{C} = \sigma^2(\mathbf{B}^\top\mathbf{B}+\sigma^2\mathbf{I})^{-1}$, measured agreement $9.7\times10^{-16}$, inverting $5\times5$ instead of $64\times64$. For $\mathbf{B}_{\mathrm{ML}}$ this is diagonal with $C_{mm} = \sigma^2/\lambda_m$ — the posterior is uncertain in inverse proportion to the variance each axis carries, and it knows this before seeing data.

The shrinkage. PPCA’s reconstruction is PCA’s, scaled per axis by $(\lambda_m-\sigma^2)/\lambda_m$ — measured to six decimals across four noise levels and five axes. At $\sigma^2 = 40$: $0.736093$ on axis $1$ down to $0.236834$ on axis $5$.

Every measured constant in this chapter

quantity	value	page
$\mathrm{tr}(\mathbf{S})$, digit “8”	$741.158872$	1001
$\lambda_1$	$151.568412$ ($20.45\%$ of the total)	1002
uncentred $\mathbf{b}_1$ vs the mean image	$0.2851^\circ$	1001
centred vs uncentred $\mathbf{b}_1$	$87.9996^\circ$	1001
rank of the centred data matrix	$52$ of $64$; $12$ dead pixels	1001
storage break-even	$M = 47$, i.e. $ND/(N+D) = 46.79$	1001
$\mathbf{b}_m^\top\mathbf{S}\mathbf{b}_m$ vs $\lambda_m$	$8.5\times10^{-14}$	1002
$200{,}000$ random unit vectors vs $\lambda_1$	$37.18\%$	1002
components for $50/90/99\%$ of the variance	$5$ / $18$ / $36$	1002
measured $J_M$ vs $\sum_{j>M}\lambda_j$	$2.8\times10^{-13}$ over all $M$	1002, 1004
Eq 10.32 vs a $100{,}001$-point grid search	$4.919350$ vs $4.919360$	1003
the Pythagoras identity, $200{,}000$ random $\mathbf{z}$	$1.7\times10^{-15}$	1003
non-orthonormal basis, same subspace	$24.728409$ vs $16.316272$	1003
share of the error in $U^\perp$	$1.000000000000$	1003
$V_M + J_M - \mathrm{tr}(\mathbf{S})$	$2.3\times10^{-13}$	1004
$200{,}000$ random orthonormal bases, $M=5$	best $624.426067$ vs $320.123369$; $0$ beat it	1004
rotating $\mathbf{B}$: $J_M$, codes	unchanged; $39.243537$	1004
code covariance off-diagonal, eigenbasis vs rotated	$5.1\times10^{-14}$ vs $37.046852$	1004
$\lambda_d$ vs $\sigma_d^2/N$	$1.4\times10^{-13}$	1005
$\kappa(\mathbf{S})/\kappa(\mathbf{X})$	$246.8358 = \kappa(\mathbf{X})$	1005
eigh at $\kappa = 10^{10}$	$5.3\times10^{3}$ relative, $18$ negatives	1005
Eckart–Young spectral error vs $\sigma_{M+1}$	$7\times10^{-14}$	1005
power-iteration rate, predicted vs observed	$0.578708$ vs $0.578541$	1005
steps to $10^{-6}$ deg at $\lambda_2/\lambda_1 = 0.99$	$1769$, against $27$ at $0.5$	1005
$N = 50$ in $D = 784$: nonzero eigenvalues	$49$	1006
Gram matrix condition number (centred)	$4.15\times10^{17}$	1006
$N\times N$ speed-up at $D = 4000$	$4565.2\times$	1006
unnormalised $\mathbf{X}\mathbf{c}_m$	$6.269\times10^{4}$ vs $1.160\times10^{1}$	1006
metres vs millimetres, unstandardised	$77.3982^\circ$; standardised, $1.2\times10^{-6}$	1007
$\mathrm{tr}$, raw vs standardised	$386.429897$ vs $2.000000 = D$	1007
NaNs from Equation 10.58	$2{,}088$	1007
test statistics vs training statistics	$15.400250$ vs $15.781992$	1007
Eq 10.70b by $400{,}000$ samples	$2.1\times10^{-3}$ relative (floor $1.6\times10^{-3}$)	1008
$\mathbf{C}$ over $200$ observations	$0.000\times10^{0}$ change	1008
$C_{mm}$ vs $\sigma^2/\lambda_m$	off-diagonal $9.7\times10^{-16}$	1008
$\sigma^2_{\mathrm{ML}}$ vs $J_M/(D-M)$	identical to $8$ decimals	1008
PPCA shrinkage at $\sigma^2 = 40$	$0.736093$ down to $0.236834$	1008
$M = 0$ baseline, RMS	$27.224233$	1009
four rules for $M$	$1$, $18$, $25$, $38$	1009
rotation vs rescaling equivariance	$8.0\times10^{-16}$ vs $59.2214^\circ$	1009
PPCA imputation vs mean-filling	$36.8\%$ better at $10\%$ missing	1009
novelty: digit “0” flagged	$100.0\%$	1009
a noisy circle’s eigenvalues	$0.501038$, $0.497606$	1009
kernel PCA on two rings	separation $0.0597 \to 7.5299$	1009

The chapter in twelve lines

1. Equation 10.1 is a covariance only if you centre. Skip it and the leading direction becomes the mean, $0.2851^\circ$ from it.
2. §10.1 fixes $M$ and chooses nothing else. Example 10.1’s vector gives errors $5$, $3$ and $0$ under three orthonormal bases.
3. Variance is a quadratic form, so maximising it under a norm constraint is an eigenvalue problem — Equation 10.15 makes the answer readable off the spectrum.
4. The deflation in Equation 10.17 is a proof, not an algorithm. One eigendecomposition gives every component.
5. §10.3 minimises something different and lands in the same place, because $V_M + J_M = \mathrm{tr}(\mathbf{S})$ is fixed.
6. The optimal coordinates are the orthogonal projection — geometry, not data — which is why §10.3.3 has only half a problem left.
7. Equation 10.32 assumes orthonormality and fails quietly without it, $24.73$ against $16.32$.
8. The objective sees $\mathbf{B}\mathbf{B}^\top$, not $\mathbf{B}$. Hence Equation 10.78’s arbitrary $\mathbf{R}$, and hence ICA.
9. Use the SVD of $\mathbf{X}$, not the eigendecomposition of $\mathbf{S}$, whenever the small eigenvalues matter.
10. When $N \ll D$, decompose the $N\times N$ Gram matrix — $4565\times$ faster at $D = 4000$ — and remember to normalise.
11. Standardising is a modelling decision. $77.3982^\circ$ says so, and so does the fact that the raw trace has no units.
12. PPCA is PCA with a story attached, and the story buys imputation, novelty and a posterior whose width you know in advance.

Back to the start: Dimensionality Reduction Overview