09_Principal_Component_Analysis

Module 8 — Principal Component Analysis (Dimensionality Reduction)

Sources: Lec 20 — PCA for Dimensionality Reduction; Bishop, Pattern Recognition and Machine Learning, §12.1 (pp. 561–570, scanned; probabilistic PCA §12.2 only introduced there). · Prev: Module 7 · Next: Module 9 — Neural Nets · Index: 00_INDEX_and_Coverage

Notation

Data ${\vec{X}}_n\in {\mathbb{R}}^D$ ($D$ = original dimension; the lecture writes $m$), $n=\mathrm{1..}N$; target dimension $M$ (lecture: $d$), $M<D$. Sample mean $\overline{\stackrel{⃗}{X}}=\frac{1}{N}\sum {\vec{X}}_n$. Covariance $S=\frac{1}{N}{\sum }_n({\vec{X}}_n-\overline{\stackrel{⃗}{X}})({\vec{X}}_n-\overline{\stackrel{⃗}{X}}{)}^T$ (symmetric, positive semidefinite). Eigen-pairs $S{\vec{u}}_i={\lambda }_i{\vec{u}}_i$, ${\lambda }_1\ge \cdots \ge {\lambda }_D\ge 0$.

Errata in the lecture notes (corrected here)

(1) The projection is $Z^{\prime }=ZE$ with $E=[{\vec{E}}_1..{\vec{E}}_d]$ of size $m\times d$ (the printed $Z{E}^T$ has mismatched dimensions). (2) “Eigenvectors corresponding to the least $(d-m)$ eigenvalues” should read the least $(m-d)$ eigenvalues. (3) Linear independence means $\sum {\beta }_j{\vec{O}}_j=\vec{0}\Rightarrow$ all ${\beta }_j=0$ (the printed "$\forall {\beta }_j\ne 0$" is garbled).

Python helper — run once, the checks below reuse it

import numpy as np
np.set_printoptions(precision=4, suppress=True)
def pca(X, bias=True):
    """Eigenvalues (descending), eigenvectors (columns), centred data Z, covariance S.
    bias=True divides by N, as in these notes (sklearn divides by N-1). Eigenvector signs are arbitrary."""
    X = np.asarray(X, float); Z = X - X.mean(0)
    S = Z.T @ Z / (len(X) if bias else len(X) - 1)
    w, V = np.linalg.eigh(S); i = np.argsort(w)[::-1]
    return w[i], V[:, i], Z, S

flowchart LR
    X["Data X (N×D)"] --> C["centre: Z = X − mean"]
    C --> S["covariance S = ZᵀZ / N"]
    S --> E["eigen-decompose<br/>keep top-M eigenvectors E"]
    E --> P["scores Z' = Z E (N×M)"]
    P --> R["reconstruct: mean + Z' Eᵀ"]

---

C43. Orthonormal Bases, Coordinates and Projections (Prerequisite)

Intuition

Coordinates relative to a rotated set of perpendicular unit axes are just dot products. PCA is a search for the best rotated axes.

Formal definitions

• A set $\{{\vec{O}}_1..{\vec{O}}_D\}$ is a basis of ${\mathbb{R}}^D$ if the vectors are linearly independent and every vector is a linear combination of them.
• It is orthonormal if ${\vec{O}}_j^T{\vec{O}}_j=1$ (unit length) and ${\vec{O}}_j^T{\vec{O}}_r=0$ for $r\ne j$.
• For an orthonormal basis, coordinates are dot products: $\vec{X}={\sum }_{j=1}^D\left({\vec{X}}^T{\vec{O}}_j\right){\vec{O}}_j.$
• Parseval: $\Vert \vec{X}{\Vert }^2={\sum }_j({\vec{X}}^T{\vec{O}}_j{)}^2$.
• Projection onto the first $d$ axes: $\hat{\vec{X}}={\sum }_{j=1}^d({\vec{X}}^T{\vec{O}}_j){\vec{O}}_j$; the residual $\vec{X}-\hat{\vec{X}}={\sum }_{j>d}({\vec{X}}^T{\vec{O}}_j){\vec{O}}_j$ is orthogonal to the subspace, and $\Vert \vec{X}-\hat{\vec{X}}{\Vert }^2={\sum }_{j>d}({\vec{X}}^T{\vec{O}}_j{)}^2$.

Derivation (the expansion formula; lecture appendix)

Write $\vec{X}={\sum }_r{\alpha }_r{\vec{O}}_r$ (possible since it is a basis). Take the inner product with ${\vec{O}}_j$: ${\vec{X}}^T{\vec{O}}_j={\sum }_r{\alpha }_r{\vec{O}}_r^T{\vec{O}}_j={\alpha }_j$, because ${\vec{O}}_r^T{\vec{O}}_j=0$ for $r\ne j$ and $=1$ for $r=j$. Hence ${\alpha }_j={\vec{X}}^T{\vec{O}}_j$. Parseval: $\Vert \vec{X}{\Vert }^2={\sum }_{r,j}{\alpha }_r{\alpha }_j{\vec{O}}_r^T{\vec{O}}_j={\sum }_j{\alpha }_j^2$. ∎

Key insights

• The projection is the closest point of the subspace to $\vec{X}$ (orthogonal projection).
• A rotation (orthonormal change of basis) preserves lengths and angles.

Worked examples

Example 1 — Very Easy · Is it orthonormal?

• Problem: Is $\{{\vec{O}}_1=\frac{1}{\sqrt{2}}(1,1),{\vec{O}}_2=\frac{1}{\sqrt{2}}(1,-1)\}$ orthonormal?
• Asked: Check.
• Concept: Definition.
• Approach: Norms and dot product.
• Solution: $\Vert {\vec{O}}_1{\Vert }^2=\frac{1}{2}(1+1)=1$; $\Vert {\vec{O}}_2{\Vert }^2=1$; ${\vec{O}}_1^T{\vec{O}}_2=\frac{1}{2}(1-1)=0$.
• Final answer: Yes.

Key lesson

Orthonormal = unit length + mutually perpendicular. (This basis is the $x,y$ axes rotated by 45°.)

Example 2 — Easy · Coordinates in a rotated basis

• Problem: Coordinates of $\vec{X}=(3,1)$ in that basis; reconstruct $\vec{X}$.
• Asked: ${\alpha }_1,{\alpha }_2$ and reconstruction.
• Concept: ${\alpha }_j={\vec{X}}^T{\vec{O}}_j$.
• Approach: Dot products.
• Solution: ${\alpha }_1=\frac{3+1}{\sqrt{2}}=2.828$; ${\alpha }_2=\frac{3-1}{\sqrt{2}}=1.414$. ${\alpha }_1{\vec{O}}_1+{\alpha }_2{\vec{O}}_2=(2,2)+(1,-1)=(3,1)$ ✓.
• Final answer: $(2.828,1.414)$.

Key lesson

Coordinates are rotated components.

Example 3 — Moderate · An orthonormal basis of ℝ³

• Problem: ${\vec{O}}_1=\frac{1}{3}(1,2,2)$, ${\vec{O}}_2=\frac{1}{3}(2,1,-2)$, ${\vec{O}}_3=\frac{1}{3}(2,-2,1)$. Verify orthonormality, find the coordinates of $\vec{X}=(3,6,0)$, and check Parseval.
• Asked: Verification, $\alpha$, norm check.
• Concept: Orthonormal basis in ${\mathbb{R}}^3$.
• Approach: Dot products.
• Solution: $\Vert {\vec{O}}_i{\Vert }^2=\frac{9}{9}=1$. ${\vec{O}}_1^T{\vec{O}}_2=\frac{2+2-4}{9}=0$; ${\vec{O}}_1^T{\vec{O}}_3=0$; ${\vec{O}}_2^T{\vec{O}}_3=0$ ✓. ${\alpha }_1=5$; ${\alpha }_2=4$; ${\alpha }_3=-2$. Reconstruction: $5{\vec{O}}_1+4{\vec{O}}_2-2{\vec{O}}_3=\frac{1}{3}(9,18,0)=(3,6,0)$ ✓. Parseval: $\Vert \vec{X}{\Vert }^2=45=25+16+4$ ✓.
• Final answer: $\alpha =(5,4,-2)$.

Python check

O = np.array([[1,2,2], [2,1,-2], [2,-2,1]]) / 3; x = np.array([3, 6, 0])
a = O @ x; print(a, O @ O.T)                              # [ 5. 4. -2.]  and the identity
print(a @ O, x @ x, a @ a)                                # [3. 6. 0.]  45  45

Key lesson

Lengths are preserved by orthonormal coordinates.

Example 4 — Hard · Project onto two of three axes

• Problem: With the basis of Example 3, project $\vec{X}=(3,6,0)$ onto $\mathrm{span}\{{\vec{O}}_1,{\vec{O}}_2\}$. Find the projection, the residual and its squared length. Then compare with using $\mathrm{span}\{{\vec{O}}_1,{\vec{O}}_3\}$.
• Asked: Projection and errors.
• Concept: Truncated expansion error.
• Approach: Drop the omitted coordinate.
• Solution: $\hat{\vec{X}}=5{\vec{O}}_1+4{\vec{O}}_2=(\frac{13}{3},\frac{14}{3},\frac{2}{3})$. Residual $=-2{\vec{O}}_3=\frac{1}{3}(-4,4,-2)$; $\Vert \cdot {\Vert }^2=4={\alpha }_3^2$ ✓. Using $\{{\vec{O}}_1,{\vec{O}}_3\}$ drops ${\alpha }_2$: error $={\alpha }_2^2=16$.
• Final answer: Error $4$ vs $16$.

Python check

proj = a[:2] @ O[:2]; print(proj, np.sum((x - proj)**2), a[1]**2)   # [4.3333 4.6667 0.6667]  4.0  16.0 (if O2 were dropped instead)

Key lesson

The error equals the sum of squares of the discarded coordinates — so discard the small ones.

Example 5 — Very Hard · Rotations and truncation error

• Problem: Show that if $Q=[{\vec{O}}_1\cdots {\vec{O}}_D]$ has orthonormal columns then $Q^{T}Q=I$, $Q{Q}^T=I$, and $\Vert Q^T\vec{X}\Vert =\Vert \vec{X}\Vert$. Then show that the squared reconstruction error of an arbitrary choice of $d$ axes from the basis, summed over a data set, equals ${\sum }_{j\text{ dropped}}{\sum }_n({\vec{X}}_n^T{\vec{O}}_j{)}^2$.
• Asked: Two proofs.
• Concept: Rotation and truncation.
• Approach: Matrix algebra.
• Solution: $(Q^{T}Q{)}_{jr}={\vec{O}}_j^T{\vec{O}}_r={\delta }_{jr}$ ⇒ $Q^{T}Q=I$. For a square $Q$, $Q^T=Q^{-1}$ ⇒ $Q{Q}^T=I$. $\Vert Q^T\vec{X}{\Vert }^2={\vec{X}}^{T}Q{Q}^T\vec{X}=\Vert \vec{X}{\Vert }^2$. Truncation: for each $n$, residual $={\sum }_{j\in \text{dropped}}({\vec{X}}_n^T{\vec{O}}_j){\vec{O}}_j$; by orthonormality its squared norm is ${\sum }_{j\in \text{dropped}}({\vec{X}}_n^T{\vec{O}}_j{)}^2$; sum over $n$. ∎
• Final answer: As shown.

Key lesson

Total error splits axis by axis — the basis of the minimum-error derivation (C45).

Common mistakes

• Using a non-unit vector for coordinates (${\alpha }_j={\vec{X}}^T{\vec{O}}_j$ needs $\Vert {\vec{O}}_j\Vert =1$).
• Forgetting orthogonality between axes.

Exam traps

• Orthonormal ⇒ both unit and orthogonal; orthogonal alone is not enough.
• Linear independence ≠ orthogonality.

Connections: C44–C45.

Mastery checklist

• Verify orthonormality.
• Compute coordinates and reconstruct.
• State Parseval and use it for truncation error.

---

C44. PCA as Maximum Variance (Bishop §12.1.1)

Intuition

Squash the data onto a line (or plane) so that the spread of the squashed points is as large as possible — you keep the most “information” (spread) in the fewest dimensions. Like photographing a pencil: shoot it from the side, not end-on.

        ╱ ● ●                  PC1 = direction of greatest spread
      ● ● ●╱                   (a tilted cloud: better than either axis)
    ● ●  ╱
   ●   ╱  ● ← PC2 is perpendicular, with much less spread

Formal derivation

Project onto a unit direction ${\vec{u}}_1$ (${\vec{u}}_1^T{\vec{u}}_1=1$; only direction matters). Each ${\vec{X}}_n\mapsto {\vec{u}}_1^T{\vec{X}}_n$. The mean of the projections is ${\vec{u}}_1^T\overline{\stackrel{⃗}{X}}$; the variance is $\frac{1}{N}{\sum }_n({\vec{u}}_1^T{\vec{X}}_n-{\vec{u}}_1^T\overline{\stackrel{⃗}{X}}{)}^2={\vec{u}}_1^{T}S{\vec{u}}_1.$ Maximise ${\vec{u}}_1^{T}S{\vec{u}}_1$ subject to ${\vec{u}}_1^T{\vec{u}}_1=1$. Lagrangian $\mathcal{L}={\vec{u}}_1^{T}S{\vec{u}}_1+{\lambda }_1(1-{\vec{u}}_1^T{\vec{u}}_1)$. $\nabla \mathcal{L}=2S{\vec{u}}_1-2{\lambda }_1{\vec{u}}_1=0\Rightarrow \boxed{S{\vec{u}}_1={\lambda }_1{\vec{u}}_1}$. So ${\vec{u}}_1$ is an eigenvector; left-multiplying by ${\vec{u}}_1^T$: variance $={\vec{u}}_1^{T}S{\vec{u}}_1={\lambda }_1$. Maximum ⇒ largest eigenvalue. Further components: maximise variance among directions orthogonal to those already chosen ⇒ eigenvectors of the next-largest eigenvalues (proof by induction). The $M$-dimensional optimum is spanned by ${\vec{u}}_1..{\vec{u}}_M$ and retains total variance ${\sum }_{i\le M}{\lambda }_i$.

Key insights

• Scores on different PCs are uncorrelated: $\mathrm{Cov}({\vec{u}}_i^T\vec{X},{\vec{u}}_j^T\vec{X})={\vec{u}}_i^{T}S{\vec{u}}_j={\lambda }_j{\vec{u}}_i^T{\vec{u}}_j=0$.
• Total variance $=\mathrm{tr}S={\sum }_{i=1}^D{\lambda }_i$.
• Cost: full eigendecomposition $O(D^3)$; first $M$ only, via the power method, $O(M{D}^2)$.

Worked examples

Example 1 — Very Easy · Diagonal covariance

• Problem: $S=\left(\begin{array}{cc}2& 0\\ 0& 1\end{array}\right)$. Principal components and variances?
• Asked: Eigen-pairs.
• Concept: Diagonal covariance.
• Approach: Read off.
• Solution: ${\lambda }_1=2,{\vec{u}}_1=(1,0)$; ${\lambda }_2=1,{\vec{u}}_2=(0,1)$.
• Final answer: PC1 along $x$ with variance 2.

Key lesson

Uncorrelated features ⇒ the axes are the PCs.

Example 2 — Easy · Correlated features

• Problem: $S=\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right)$. Find the PCs and compare the variance along ${\vec{u}}_1$ with the variance along $(1,0)$.
• Asked: Eigen-pairs and a comparison.
• Concept: $\lambda ={\vec{u}}^{T}S\vec{u}$.
• Approach: $\det (S-\lambda I)=0$.
• Solution: $(3-\lambda {)}^2-1=0\Rightarrow \lambda =4,2$. $\lambda =4$: ${\vec{u}}_1=\frac{1}{\sqrt{2}}(1,1)$. $\lambda =2$: ${\vec{u}}_2=\frac{1}{\sqrt{2}}(1,-1)$. Variance along $(1,0)$: $3<4$.
• Final answer: $(4,\frac{1}{\sqrt{2}}(1,1))$, $(2,\frac{1}{\sqrt{2}}(1,-1))$; axis-aligned variance $3$.

Python check

print(np.linalg.eigh(np.array([[3, 1], [1, 3.]])))        # eigenvalues [2 4], eigenvectors ±(1,−1)/√2, ±(1,1)/√2

Key lesson

Correlation tilts the best direction off the axes.

Example 3 — Moderate · A nearly one-dimensional cloud

• Problem: Deviations of height and arm-span from the mean for four people: $(-2,-1),(-1,-1),(1,1),(2,1)$ (mean zero). Find $S$, the first PC, its variance and the fraction of total variance kept.
• Asked: $S,{\vec{u}}_1,{\lambda }_1$, fraction.
• Concept: PCA.
• Approach: $S=\frac{1}{4}\sum \vec{X}{\vec{X}}^T$.
• Solution: $S_{11}=\frac{4+1+1+4}{4}=2.5$; $S_{22}=1$; $S_{12}=\frac{2+1+1+2}{4}=1.5$. $\mathrm{tr}S=3.5$, $\det S=0.25$. $\lambda =\frac{3.5\pm \sqrt{11.25}}{2}=3.4271,0.0729$. ${\vec{u}}_1$: $(2.5-3.4271)u_x+1.5u_y=0\Rightarrow u_y=0.6180u_x$; normalised ${\vec{u}}_1=(0.8507,0.5257)$. Fraction $=\frac{3.4271}{3.5}=97.9\%$.
• Final answer: ${\vec{u}}_1=(0.851,0.526)$, ${\lambda }_1=3.427$, $97.9\%$ of variance.

Python check

X = [(-2,-1), (-1,-1), (1,1), (2,1)]
w, V, Z, S = pca(X); print(S, w, V[:, 0], w[0] / w.sum())  # [[2.5 1.5][1.5 1.]]  [3.4271 0.0729]  ±[0.8507 0.5257]  0.9792

Key lesson

A nearly 1-D cloud compresses almost losslessly.

Example 4 — Hard · Retained variance and the Rayleigh quotient

• Problem: $S=\mathrm{diag}(5,3,2)$. (a) Variance retained by $M=1,2$. (b) The variance along the unit direction $\vec{u}=(1,1,0)/\sqrt{2}$ and why it is below ${\lambda }_1$.
• Asked: Fractions and a directional variance.
• Concept: Rayleigh quotient.
• Approach: ${\vec{u}}^{T}S\vec{u}$.
• Solution: (a) Total $=10$. $M=1$: $50\%$; $M=2$: $80\%$. (b) ${\vec{u}}^{T}S\vec{u}=\frac{1}{2}(5+3)=4<5$. In general ${\vec{u}}^{T}S\vec{u}={\sum }_i{\lambda }_i({\vec{u}}^T{\vec{u}}_i{)}^2$ is a weighted average of the eigenvalues (weights sum to $1$) ⇒ $\le {\lambda }_1$ with equality only for $\vec{u}={\vec{u}}_1$.
• Final answer: $50\%,80\%$; directional variance $4$.

Python check

S = np.diag([5, 3, 2.]); u = np.array([1, 1, 0]) / np.sqrt(2)
print(u @ S @ u, np.cumsum([5, 3, 2]) / 10)               # 4.0  [0.5 0.8 1. ]

Key lesson

The Rayleigh quotient is bounded by the extreme eigenvalues.

Example 5 — Very Hard · Scores are uncorrelated

• Problem: For Example 3 compute the scores on PC1 and PC2 for the four points, verify their variances equal ${\lambda }_1,{\lambda }_2$ and that the scores are uncorrelated. Also prove uncorrelatedness in general.
• Asked: Numerical and general proof.
• Concept: Decorrelation.
• Approach: Project.
• Solution: ${\vec{u}}_1=(0.8507,0.5257)$, ${\vec{u}}_2=(-0.5257,0.8507)$. Scores $z_1$: $-2.2271,-1.3764,1.3764,2.2271$; $z_2$: $0.2007,-0.3250,0.3250,-0.2007$. $\mathrm{Var}(z_1)=3.4273$ ✓ $={\lambda }_1$; $\mathrm{Var}(z_2)=0.0730$ ✓. $\mathrm{Cov}\approx 0$ ✓. General: $\mathrm{Cov}(z_i,z_j)={\vec{u}}_i^{T}S{\vec{u}}_j={\lambda }_j{\vec{u}}_i^T{\vec{u}}_j=0$ for $i\ne j$, since eigenvectors of a symmetric matrix with different eigenvalues are orthogonal. ∎
• Final answer: Variances $3.427,0.073$; covariance $0$.

Python check

scores = Z @ V                                             # signs of columns may differ from the text
print(scores.var(0), np.cov(scores.T, bias=True))          # [3.4271 0.0729]   diag(3.4271, 0.0729), off-diagonal 0

Key lesson

PCA produces uncorrelated coordinates — hence its other name, the Karhunen–Loève transform.

Common mistakes

• Not centring (variance is about the mean).
• Forgetting the unit-norm constraint (the variance could be made infinite).

Exam traps

• Variance along PC $i$ is ${\lambda }_i$; total variance is $\mathrm{tr}S$.
• PCA is unsupervised.

Connections: C45 (equivalent view), C46 (algorithm), C48 (Fisher comparison).

Mastery checklist

• Derive $S\vec{u}=\lambda \vec{u}$ via a Lagrange multiplier.
• Compute PCs of a $2\times 2$ covariance.
• Prove uncorrelatedness of scores.

---

C45. PCA as Minimum Reconstruction Error (Lecture §20.4; Bishop §12.1.2)

Intuition

Instead of “keep the spread”, ask “which $M$-dimensional flat surface lies closest to the data on average?” Remarkably, the answer is the same subspace.

Formal derivation (lecture, step by step)

Take a complete orthonormal basis $\{{\vec{O}}_j{\}}_{j=1}^D$ and approximate each data point ${\widetilde{\stackrel{⃗}{X}}}_n={\sum }_{j=1}^M{\alpha }_{nj}{\vec{O}}_j+{\sum }_{j=M+1}^D{\beta }_j{\vec{O}}_j,$ with coefficients ${\alpha }_{nj}$ depending on $n$ but ${\beta }_j$ the same for all points. Distortion $J=\frac{1}{N}{\sum }_n\Vert {\vec{X}}_n-{\widetilde{\stackrel{⃗}{X}}}_n{\Vert }^2=\frac{1}{N}{\sum }_n[{\sum }_{j\le M}({\vec{X}}_n^T{\vec{O}}_j-{\alpha }_{nj}{)}^2+{\sum }_{j>M}({\vec{X}}_n^T{\vec{O}}_j-{\beta }_j{)}^2]$ (by orthonormality). Minimising over the coefficients: $\frac{\partial J}{\partial {\alpha }_{nj}}=0\Rightarrow {\alpha }_{nj}={\vec{X}}_n^T{\vec{O}}_j;\frac{\partial J}{\partial {\beta }_j}=0\Rightarrow {\beta }_j={\overline{\stackrel{⃗}{X}}}^T{\vec{O}}_j.$ So ${\widetilde{\stackrel{⃗}{X}}}_n={\sum }_{j\le M}({\vec{X}}_n^T{\vec{O}}_j){\vec{O}}_j+{\sum }_{j>M}({\overline{\stackrel{⃗}{X}}}^T{\vec{O}}_j){\vec{O}}_j$ and ${\vec{X}}_n-{\widetilde{\stackrel{⃗}{X}}}_n={\sum }_{j>M}(({\vec{X}}_n-\overline{\stackrel{⃗}{X}}{)}^T{\vec{O}}_j){\vec{O}}_j$ — lying in the space orthogonal to the principal subspace. Then $J={\sum }_{j=M+1}^D\frac{1}{N}{\sum }_n[({\vec{X}}_n-\overline{\stackrel{⃗}{X}}{)}^T{\vec{O}}_j{]}^2={\sum }_{j=M+1}^D{\vec{O}}_j^{T}S{\vec{O}}_j.$ Minimise subject to ${\vec{O}}_j^T{\vec{O}}_j=1$: $\mathcal{L}={\sum }_{j>M}[{\vec{O}}_j^{T}S{\vec{O}}_j+{\lambda }_j(1-{\vec{O}}_j^T{\vec{O}}_j)]$; $\partial \mathcal{L}/\partial {\vec{O}}_j=2S{\vec{O}}_j-2{\lambda }_j{\vec{O}}_j=0\Rightarrow S{\vec{O}}_j={\lambda }_j{\vec{O}}_j$, giving ${\vec{O}}_j^{T}S{\vec{O}}_j={\lambda }_j$. Hence $\boxed{J_{\min }=\sum _{j=M+1}^D{\lambda }_j,}$ attained by discarding the eigenvectors with the $D-M$ smallest eigenvalues, i.e. keeping the $M$ largest. (Covariance matrices are symmetric PSD, so eigenvalues are real and $\ge 0$.)

Key insights

• Max-variance and min-error give the same principal subspace (total variance $=\sum \lambda$ is fixed, so keeping more variance = losing less error).
• The offsets ${\beta }_j$ say: in the discarded directions, replace the point’s coordinate by the mean’s coordinate.
• Error curve (Bishop Fig. 12.4b): $J(M)={\sum }_{j>M}{\lambda }_j$ decreases as $M$ grows; $J(D)=0$.

Worked examples

Example 1 — Very Easy · Error = discarded eigenvalues

• Problem: Eigenvalues $(5,3,2,1)$. Minimum $J$ for $M=2$.
• Asked: $J$.
• Concept: $J={\sum }_{j>M}{\lambda }_j$.
• Approach: Sum the tail.
• Solution: $2+1=3$.
• Final answer: $J=3$.

Key lesson

Error = the discarded eigenvalues.

Example 2 — Easy · How many components for 90 %?

• Problem: Eigenvalues $(4,2.5,1.5,1,0.5,0.5)$. Smallest $M$ retaining $\ge 90\%$ of the variance.
• Asked: $M$.
• Concept: Cumulative variance.
• Approach: Cumulative sums (total $10$).
• Solution: $M=1$: $40\%$; $2$: $65\%$; $3$: $80\%$; $4$: $90\%$ ✓.
• Final answer: $M=4$ (error $J=1$).

Python check

lam = np.array([4, 2.5, 1.5, 1, .5, .5]); print(np.cumsum(lam) / lam.sum())    # [0.4 0.65 0.8 0.9 0.95 1.]

Key lesson

The lecture notes that no principled automatic choice of $M$ exists — thresholds like this are a heuristic.

Example 3 — Moderate · Keep the right axis

• Problem: Points $(1,1),(3,1),(2,4)$; mean $(2,2)$. Using the (not necessarily optimal) basis ${\vec{O}}_1=(1,0)$, ${\vec{O}}_2=(0,1)$ and $M=1$, compute $J$ if ${\vec{O}}_2$ is the discarded axis and if ${\vec{O}}_1$ is discarded.
• Asked: Two distortions.
• Concept: Formula for $J$.
• Approach: $J={\vec{O}}_{disc}^{T}S{\vec{O}}_{disc}$.
• Solution: $S_{11}=\frac{2}{3}$; $S_{22}=2$; $S_{12}=0$. Discard ${\vec{O}}_2$: $J=2$. Discard ${\vec{O}}_1$: $J=\frac{2}{3}$. Direct check (discard ${\vec{O}}_2$, replace $y$ by the mean $2$): errors $-1,-1,2$ ⇒ $\frac{1+1+4}{3}=2$ ✓.
• Final answer: $J=2$ vs $J=\frac{2}{3}$.

Key lesson

Keep the high-variance axis, discard the low-variance one.

Example 4 — Hard · One direction, three choices

• Problem: $S=\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right)$, $M=1$. Compute $J$ if the discarded unit direction is (a) $(1,0)$, (b) ${\vec{u}}_2=\frac{1}{\sqrt{2}}(1,-1)$, (c) ${\vec{u}}_1=\frac{1}{\sqrt{2}}(1,1)$.
• Asked: Three distortions.
• Concept: $J={\vec{O}}^{T}S\vec{O}$.
• Approach: Evaluate the quadratic form.
• Solution: (a) $3$. (b) $\frac{1}{2}(3-1-1+3)=2$. (c) $\frac{1}{2}(3+1+1+3)=4$.
• Final answer: $3,2,4$; the minimum $2={\lambda }_2$ occurs when discarding the eigenvector of the smaller eigenvalue.

Python check

S = np.array([[3, 1], [1, 3.]])
for o in ([1, 0], [1, -1], [1, 1]):
    o = np.array(o) / np.linalg.norm(o); print(o @ S @ o)  # 3.0  2.0  4.0

Key lesson

$J\in [{\lambda }_{\min },{\lambda }_{\max }]$ for any one-direction discard.

Example 5 — Very Hard · Why the smallest eigenvector is optimal

• Problem: Prove that if $\vec{O}$ is a unit vector then ${\vec{O}}^{T}S\vec{O}\ge {\lambda }_{\min }$ with equality iff $\vec{O}$ is an eigenvector for ${\lambda }_{\min }$; deduce the PCA optimality for $M=D-1$ and verify with the data of C44 Ex. 3.
• Asked: Proof and check.
• Concept: Rayleigh quotient.
• Approach: Expand in the eigenbasis.
• Solution: Write $\vec{O}={\sum }_i{c}_i{\vec{u}}_i$ with $\sum c_i^2=1$. ${\vec{O}}^{T}S\vec{O}={\sum }_i{\lambda }_i{c}_i^2\ge {\lambda }_{\min }\sum c_i^2={\lambda }_{\min }$, equality iff $c_i=0$ whenever ${\lambda }_i>{\lambda }_{\min }$. For $M=D-1$ exactly one direction is discarded, so $J_{\min }={\lambda }_D$, achieved by the least-variance eigenvector. Check: C44 Ex. 3 data, discarding ${\vec{u}}_2$: errors $z_2^2=(0.0403,0.1056,0.1056,0.0403)$, mean $=0.0730={\lambda }_2$ ✓; discarding $(1,0)$ instead: $J=S_{11}=2.5$.
• Final answer: $J_{\min }={\lambda }_D$; numeric check $0.073$ vs $2.5$ for a poor choice.

Key lesson

The reconstruction error is exactly the variance in the discarded direction.

Common mistakes

• Confusing “keep the eigenvectors of the smallest eigenvalues” with discarding them.
• Forgetting that ${\beta }_j$ uses the mean.

Exam traps

• $J_{\min }={\sum }_{j>M}{\lambda }_j$ (the sum of discarded eigenvalues).
• If eigenvalues are equal, any basis of their eigenspace is equivalent.

Connections: C43, C44, C48 (reconstruction).

Mastery checklist

• Reproduce the derivation of ${\alpha }_{nj},{\beta }_j$.
• Derive $J={\sum }_{j>M}{\lambda }_j$.
• Compute reconstruction errors.

---

C46. The PCA Algorithm, Standardisation and Whitening

Intuition

Centre the data, find the eigen-directions of its covariance, and express each point by its coordinates along the top ones. Optionally rescale so every direction has unit variance (whitening), or work with correlations (standardising) so units do not matter.

Algorithm (lecture, with the corrections above)

1. Subtract each feature’s mean: ${\hat{\vec{X}}}_i={\vec{X}}_i-\overline{\stackrel{⃗}{X}}$; stack as $Z$ ($n\times m$).
2. Form the $m\times m$ covariance matrix $S=\frac{1}{n}{Z}^{T}Z$ (the lecture uses $Z^{T}Z$ — same eigenvectors, eigenvalues scaled by $n$).
3. Find the $d$ largest eigenvalues.
4. Take the corresponding unit eigenvectors as columns of $E=[{\vec{E}}_1..{\vec{E}}_d](m\times d)$.
5. Project: $\boxed{Z^{\prime }=ZE}$ ($n\times d$). Reconstruction: ${\widetilde{\stackrel{⃗}{X}}}_i=\overline{\stackrel{⃗}{X}}+E{\vec{z}}_i^{\prime }$.

Standardising: dividing each centred feature by its standard deviation gives zero mean, unit variance; the covariance matrix then equals the correlation matrix ${\rho }_{ij}=\frac{S_{ij}}{{\sigma }_i{\sigma }_j}$ ($\rho =1$ perfect positive correlation, $0$ uncorrelated).

Whitening (sphering): with $S=U\Lambda U^T$, define ${\vec{y}}_n={\Lambda }^{-1/2}{U}^T({\vec{X}}_n-\overline{\stackrel{⃗}{X}})$. Then $\frac{1}{N}{\sum }_n{\vec{y}}_n{\vec{y}}_n^T={\Lambda }^{-1/2}{U}^{T}SU{\Lambda }^{-1/2}={\Lambda }^{-1/2}\Lambda {\Lambda }^{-1/2}=I,$ zero mean and identity covariance: all variables decorrelated and unit-variance.

Key insights

• PCA is scale-dependent: standardise when units differ (e.g. kilograms vs metres).
• Choosing $d$: no good automatic method (variance threshold or the elbow of the eigenvalue spectrum).
• Centring is needed for the covariance to equal $\frac{1}{n}{Z}^{T}Z$.

Worked examples

Example 1 — Very Easy · Centre and measure the spread

• Problem: Centre the data $\{2,4,6\}$ (one feature) and give the covariance.
• Asked: Centred data and variance.
• Concept: Steps 1–2.
• Approach: Mean $=4$.
• Solution: $Z=(-2,0,2)$; variance $=\frac{4+0+4}{3}=2.667$.
• Final answer: $(-2,0,2)$; $2.667$.

Key lesson

Centre first.

Example 2 — Easy · A covariance matrix

• Problem: Two features with data $(1,2),(3,2),(2,5)$. Centre and compute $S$.
• Asked: $S$.
• Concept: Covariance matrix.
• Approach: Means $(2,3)$.
• Solution: $Z=\{(-1,-1),(1,-1),(0,2)\}$. $S_{11}=\frac{2}{3}$; $S_{22}=2$; $S_{12}=0$.
• Final answer: $S=\mathrm{diag}(\frac{2}{3},2)$.

Python check

print(pca([(1, 2), (3, 2), (2, 5)])[3])                    # [[0.6667 0.][0. 2.]]

Key lesson

Zero covariance ⇒ the PCs are the coordinate axes.

Example 3 — Moderate · Project, reconstruct, measure the error

• Problem: Full PCA (to $d=1$) of the points $(-2,-1),(-1,-1),(1,1),(2,1)$: give $Z^{\prime }$ and the reconstruction of the first point and its error.
• Asked: $Z^{\prime }$, ${\widetilde{\stackrel{⃗}{X}}}_1$, error.
• Concept: $Z^{\prime }=ZE$.
• Approach: $E={\vec{u}}_1=(0.8507,0.5257{)}^T$.
• Solution: $Z^{\prime }=ZE=(-2.2271,-1.3764,1.3764,2.2271{)}^T$ (a $4\times 1$ matrix). Reconstruction of ${\vec{X}}_1$: $z_1^{\prime }{\vec{u}}_1=(-1.8946,-1.1708)$. Error vector $=(-0.1054,0.1708)$; $\Vert e{\Vert }^2=0.0403$. Mean squared error over the four points $=0.0730={\lambda }_2$ ✓.
• Final answer: MSE $={\lambda }_2=0.073$.

Python check

w, V, Z, S = pca([(-2,-1), (-1,-1), (1,1), (2,1)])
E = V[:, :1]; Zp = Z @ E; rec = Zp @ E.T                  # N×1 scores, reconstruction (mean is 0 here)
print(Zp.ravel(), rec[0], ((Z - rec)**2).sum(1).mean())   # ±[2.2271 1.3764 …]  [-1.8944 -1.1708]  0.0729

Key lesson

Algorithm and theory agree: MSE $=$ the discarded eigenvalue.

Example 4 — Hard · Grams vs kilograms

• Problem: Two features measured in different units: $A=(100,200,300)$ (grams), $B=(1,3,2)$ (kilograms). Compare the first PC on raw data and on standardised data.
• Asked: Two PC1’s.
• Concept: Scale dependence; correlation matrix.
• Approach: Raw $S$, then $\rho$.
• Solution: Means $200$ and $2$. $S_{AA}=6666.7$; $S_{BB}=0.6667$; $S_{AB}=33.33$. Raw: ${\lambda }_1\approx 6666.8$, ${\vec{u}}_1\approx (1,0.005)$ — essentially feature $A$ alone (units dominate). Standardised: ${\sigma }_A=81.65$, ${\sigma }_B=0.8165$; $\rho =0.5$; correlation matrix $\left(\begin{array}{cc}1& 0.5\\ 0.5& 1\end{array}\right)$ ⇒ $\lambda =1.5,0.5$, ${\vec{u}}_1=\frac{1}{\sqrt{2}}(1,1)$ — both features contribute equally.
• Final answer: Raw PC1 $\approx$ feature $A$; standardised PC1 $=\frac{1}{\sqrt{2}}(1,1)$.

Python check

X = np.c_[[100, 200, 300.], [1, 3, 2.]]
print(pca(X)[:2])                                         # [6666.83  0.5]   PC1 ≈ ±(1, 0.005)
print(pca((X - X.mean(0)) / X.std(0))[:2])                # [1.5 0.5]        PC1 = ±(0.7071, 0.7071)

Key lesson

Standardise when features have different scales.

Example 5 — Very Hard · Whitening

• Problem: $S=\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right)$ (so $U=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$, $\Lambda =\mathrm{diag}(4,2)$). Show that whitening gives identity covariance, and whiten the (centred) point $\vec{x}=(2,0)$.
• Asked: Proof and numeric image.
• Concept: Whitening.
• Approach: Matrix identity.
• Solution: $U^{T}SU=\Lambda$ ⇒ $\mathrm{Cov}(\vec{y})={\Lambda }^{-1/2}\Lambda {\Lambda }^{-1/2}=I$ ✓. Point: $U^T\vec{x}=(1.4142,1.4142)$; ${\Lambda }^{-1/2}=\mathrm{diag}(\frac{1}{2},\frac{1}{\sqrt{2}})$ ⇒ $\vec{y}=(0.7071,1.0)$.
• Final answer: $\vec{y}=(0.707,1.0)$; $\mathrm{Cov}(\vec{y})=I$.

Python check

S = np.array([[3, 1], [1, 3.]]); w, U = np.linalg.eigh(S); i = np.argsort(w)[::-1]; w, U = w[i], U[:, i]
print(np.diag(w**-.5) @ U.T @ np.array([2, 0.]))          # ±[0.7071 1.]   (signs depend on eigenvector orientation)
print(np.diag(w**-.5) @ U.T @ S @ U @ np.diag(w**-.5))    # identity

Key lesson

Whitening = rotate to the PC axes, then divide each coordinate by $\sqrt{{\lambda }_i}$.

Common mistakes

• Using $Z{E}^T$ (wrong dimensions) instead of $ZE$.
• Forgetting to add the mean back when reconstructing.

Exam traps

• Divide by $n$ or $n-1$: eigenvectors identical, eigenvalues rescaled.
• Whitening divides by $\sqrt{\lambda }$, not $\lambda$.

Connections: C44–C45, k-means preprocessing (C36), logistic / SVM preprocessing.

Mastery checklist

• Execute the 5-step algorithm.
• Explain standardisation vs raw PCA.
• Derive whitening.

---

C47. PCA When $N<D$ (High-Dimensional Data; Bishop §12.1.4)

Intuition

If you have 200 face images of $10^6$ pixels each, the covariance is $10^6\times 10^6$ — impossible — but the data only span an at-most-$199$-dimensional subspace. Solve a small $N\times N$ eigenproblem instead and map the eigenvectors back (this is how “eigenfaces” are computed).

Formal derivation

Let $X$ be the $N\times D$ centred data matrix (rows $({\vec{X}}_n-\overline{\stackrel{⃗}{X}}{)}^T$). Then $S=\frac{1}{N}{X}^{T}X$ and $S{\vec{u}}_i={\lambda }_i{\vec{u}}_i$ reads $\frac{1}{N}{X}^{T}X{\vec{u}}_i={\lambda }_i{\vec{u}}_i$. Multiply by $X$ and set ${\vec{v}}_i=X{\vec{u}}_i$: $\frac{1}{N}X{X}^T{\vec{v}}_i={\lambda }_i{\vec{v}}_i,$ an eigenproblem for the $N\times N$ matrix $\frac{1}{N}X{X}^T$ with the same non-zero eigenvalues. Conversely, multiply by $X^T$: $\frac{1}{N}{X}^{T}X(X^T{\vec{v}}_i)={\lambda }_i(X^T{\vec{v}}_i)$, so $X^T{\vec{v}}_i$ is an eigenvector of $S$; normalising ($\Vert {\vec{v}}_i\Vert =1$): $\boxed{{\vec{u}}_i=\frac{1}{(N{\lambda }_i{)}^{1/2}}{X}^T{\vec{v}}_i.}$ Rank: $N$ centred points span at most $N-1$ dimensions ⇒ at least $D-N+1$ eigenvalues of $S$ are $0$. Cost $O(N^3)$ instead of $O(D^3)$.

Key insights

• Never form the $D\times D$ matrix when $N<D$.
• PCA with $M>N-1$ is pointless.

Worked examples

Example 1 — Very Easy · Rank bound

• Problem: $N=3$ points in $D=100$ dimensions. Maximum number of non-zero eigenvalues of $S$?
• Asked: Rank bound.
• Concept: $\mathrm{rank}\le N-1$.
• Approach: Centred points sum to zero.
• Solution: $N-1=2$.
• Final answer: At most $2$ (so $98=D-N+1$ eigenvalues equal $0$).

Key lesson

Centring costs one dimension.

Example 2 — Easy · Counting zero eigenvalues

• Problem: How many zero eigenvalues does $S$ have for $N=200$, $D=10^6$?
• Asked: Count.
• Concept: $D-N+1$.
• Approach: Subtract.
• Solution: $10^6-200+1=999,801$.
• Final answer: $999,801$.

Key lesson

Almost all directions carry no variance.

Example 3 — Moderate · The small eigenproblem

• Problem: $N=3$, $D=4$ centred data $X$ with rows $(1,0,1,0),(-1,0,1,0),(0,0,-2,0)$. Find the eigenvalues of $\frac{1}{N}X{X}^T$.
• Asked: ${\lambda }_i$.
• Concept: Small eigenproblem.
• Approach: $G=X{X}^T$.
• Solution: $G=\left(\begin{array}{ccc}2& 0& -2\\ 0& 2& -2\\ -2& -2& 4\end{array}\right)$. Row sums are $0$ ⇒ $\vec{1}$ is a null vector (eigenvalue $0$). Trace $=8$. Others: $\mu =2$ with $\vec{v}=\frac{1}{\sqrt{2}}(-1,1,0)$ and $\mu =6$ with $\vec{v}=\frac{1}{\sqrt{6}}(1,1,-2)$. Dividing by $N=3$: $\lambda =(2,\frac{2}{3},0)$.
• Final answer: $\lambda =2,\frac{2}{3},0$ (trace $\frac{8}{3}$ ✓).

Python check

Xn = np.array([[1,0,1,0], [-1,0,1,0], [0,0,-2,0.]])
print(np.linalg.eigvalsh(Xn @ Xn.T / 3))                  # [0. 0.6667 2.]

Key lesson

Solve a $3\times 3$ problem instead of a $4\times 4$ one — scaling to huge $D$ is the point.

Example 4 — Hard · Map back to the big space

• Problem: For Example 3 recover the eigenvectors ${\vec{u}}_i$ of the $4\times 4$ covariance via ${\vec{u}}_i=X^T{\vec{v}}_i/\sqrt{N{\lambda }_i}$ and verify $S\vec{u}=\lambda \vec{u}$.
• Asked: ${\vec{u}}_1,{\vec{u}}_2$.
• Concept: Mapping back.
• Approach: Use the boxed formula.
• Solution: For ${\lambda }_1=2$ ($N\lambda =6$), $\vec{v}=\frac{1}{\sqrt{6}}(1,1,-2)$: $X^T\vec{v}=\frac{1}{\sqrt{6}}(0,0,6,0)$; divide by $\sqrt{6}$: ${\vec{u}}_1=(0,0,1,0)$, unit length ✓. $S=\frac{1}{3}{X}^{T}X=\mathrm{diag}(\frac{2}{3},0,2,0)$ ⇒ $S{\vec{u}}_1=2{\vec{u}}_1$ ✓. For ${\lambda }_2=\frac{2}{3}$ ($N\lambda =2$), $\vec{v}=\frac{1}{\sqrt{2}}(-1,1,0)$: $X^T\vec{v}=\frac{1}{\sqrt{2}}(-2,0,0,0)$; divide by $\sqrt{2}$: ${\vec{u}}_2=(-1,0,0,0)$ ✓, $S{\vec{u}}_2=\frac{2}{3}{\vec{u}}_2$ ✓.
• Final answer: PCs are the coordinate axes $\pm {\vec{e}}_3,\pm {\vec{e}}_1$ with variances $2,\frac{2}{3}$.

Python check

lam, Vv = np.linalg.eigh(Xn @ Xn.T / 3)
for l, v in zip(lam[::-1], Vv[:, ::-1].T):
    if l > 1e-9:
        u = Xn.T @ v / np.sqrt(3 * l); print(round(l, 4), u, np.allclose(Xn.T @ Xn / 3 @ u, l * u))
# 2.0 ±[0 0 1 0] True     0.6667 ±[1 0 0 0] True

Key lesson

The two-step method reproduces the direct answer.

Example 5 — Very Hard · Cost comparison

• Problem: Compare costs for $N=100$ images, $D=10^6$ pixels, using (a) the $D\times D$ eigendecomposition, (b) the $N\times N$ route, (c) $M=10$ components by the power method on $S$. Also state how many meaningful components exist.
• Asked: Operation counts and rank.
• Concept: Complexity.
• Approach: $O(D^3)$, $O(N^3)$, $O(M{D}^2)$.
• Solution: (a) $D^3=10^{18}$. (b) $N^3=10^6$ (plus forming $X{X}^T$ costs $N^{2}D=10^{10}$ and mapping back $O(NDM)$). (c) $M{D}^2=10^{13}$. Meaningful components: at most $N-1=99$.
• Final answer: $10^{18}$ vs $\approx 10^{10}$ vs $10^{13}$; $\le 99$ components.

Key lesson

The $N\times N$ trick turns an impossible computation into a trivial one.

Common mistakes

• Forgetting to normalise ${\vec{u}}_i$ (it needs the $(N{\lambda }_i{)}^{-1/2}$ factor).
• Using the uncentred $X{X}^T$.

Exam traps

• Non-zero eigenvalues of $X{X}^T/N$ and $X^{T}X/N$ coincide.
• ${\vec{v}}_i=X{\vec{u}}_i$ is not normalised unless scaled.

Connections: C44–C46; singular value decomposition; kernel PCA.

Mastery checklist

• State the rank bound.
• Derive ${\vec{u}}_i=X^T{\vec{v}}_i/\sqrt{N{\lambda }_i}$.
• Compare computational costs.

---

C48. Applications of PCA and Comparison with Fisher’s Linear Discriminant

Intuition

PCA is used for compression, preprocessing / decorrelating, visualisation (project to 2-D) and feature extraction. It ignores class labels; Fisher’s discriminant uses them to find the direction that best separates classes.

Facts

• Compression: replace ${\vec{X}}_n\in {\mathbb{R}}^D$ by $M$ numbers $({\vec{X}}_n^T{\vec{u}}_i{)}_{i\le M}$; reconstruct $\overline{\stackrel{⃗}{X}}+{\sum }_{i\le M}(({\vec{X}}_n-\overline{\stackrel{⃗}{X}}{)}^T{\vec{u}}_i){\vec{u}}_i$ (Bishop eq. 12.19–12.20). Smaller $M$ ⇒ higher compression, larger error $J={\sum }_{i>M}{\lambda }_i$.
• Visualisation: plot $({\vec{X}}_n^T{\vec{u}}_1,{\vec{X}}_n^T{\vec{u}}_2)$ (Bishop’s oil-flow example).
• Pre-processing: standardisation / whitening (C46).
• Fisher’s linear discriminant (two classes, within-class scatter $S_W$): the direction maximising $J(\vec{w})=\frac{({\vec{w}}^T({\vec{m}}_2-{\vec{m}}_1){)}^2}{{\vec{w}}^T{S}_W\vec{w}}$ is $\vec{w}\propto S_W^{-1}({\vec{m}}_2-{\vec{m}}_1)$.
• Related: canonical correlation analysis (CCA) handles two variable sets; probabilistic PCA (Bishop §12.2) casts PCA as a latent-variable Gaussian model (maximum likelihood, EM, Bayesian choice of $M$) — introduced but not developed in the scanned pages.

A real-data demo: the 4 iris measurements

from sklearn.datasets import load_iris
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler
Xi = load_iris().data                                     # 150 flowers × 4 measurements (cm)
print(PCA().fit(Xi).explained_variance_ratio_)            # [0.9246 0.0531 0.0171 0.0052] → 2 PCs keep 97.8 %
print(PCA().fit(StandardScaler().fit_transform(Xi)).explained_variance_ratio_)   # [0.7296 0.2285 0.0367 0.0052]

Same data, different story once you standardise — C46 Example 4 in real life.

Worked examples

Example 1 — Very Easy · Compression ratio

• Problem: Images of $28\times 28$ pixels ($D=784$) are compressed to $M=50$ PCA scores. Compression ratio per image?
• Asked: Ratio.
• Concept: Compression.
• Approach: $D/M$ (ignoring the shared mean and basis).
• Solution: $784/50=15.7$.
• Final answer: About $15.7\times$ fewer numbers per image.

Key lesson

The shared basis is amortised over the data set.

Example 2 — Easy · Error and retained variance

• Problem: Eigenvalue spectrum $(10,6,3,1,0.5,0.5)$. $J$ and retained variance for $M=2$.
• Asked: $J$, percentage.
• Concept: $J={\sum }_{i>M}{\lambda }_i$.
• Approach: Total $=21$.
• Solution: $J=3+1+0.5+0.5=5$; retained $=16/21=76.2\%$.
• Final answer: $J=5$; $76.2\%$.

Key lesson

Each extra component adds its eigenvalue to the retained variance.

Example 3 — Moderate · A 2-D picture of 3-D data

• Problem: Using the orthonormal basis of C43 (Ex. 3) as “principal axes” for the point $\vec{X}=(3,6,0)$ with $M=2$: give the 2-D visualisation coordinates and the reconstruction.
• Asked: Scores and reconstruction.
• Concept: Projection for display.
• Approach: ${\alpha }_1,{\alpha }_2$.
• Solution: Scores $(5,4)$. Reconstruction $(\frac{13}{3},\frac{14}{3},\frac{2}{3})=(4.33,4.67,0.67)$; error $\Vert \cdot {\Vert }^2=4$.
• Final answer: Plot at $(5,4)$; reconstruction error $4$.

Key lesson

The picture shows ${\alpha }_1,{\alpha }_2$ only; ${\alpha }_3$ is the lost information.

Example 4 — Hard · PCA is label-blind

• Problem: Two classes in 2-D with means $(0,-1)$ and $(0,1)$; within-class covariance $S_W=\mathrm{diag}(100,1)$ and total covariance dominated by the $x$-direction (large within-class spread). Find the PCA direction and Fisher’s direction; compute Fisher’s criterion for each.
• Asked: Two directions, two scores.
• Concept: Unsupervised vs supervised projection.
• Approach: ${\vec{w}}_F\propto S_W^{-1}({\vec{m}}_2-{\vec{m}}_1)$.
• Solution: PCA’s first direction is the largest-variance axis, ${\vec{w}}_{PCA}=(1,0)$. Fisher: ${\vec{m}}_2-{\vec{m}}_1=(0,2)$; $S_W^{-1}=\mathrm{diag}(0.01,1)$ ⇒ ${\vec{w}}_F\propto (0,1)$. Criterion: $J({\vec{w}}_{PCA})=\frac{0^2}{100}=0$; $J({\vec{w}}_F)=\frac{2^2}{1}=4$.
• Final answer: PCA keeps $x$ (class separation $0$); Fisher keeps $y$ (criterion $4$).

Python check

Sw = np.diag([100, 1.]); d = np.array([0, 2.])
wf = np.linalg.solve(Sw, d); crit = lambda w: (w @ d)**2 / (w @ Sw @ w)
print(wf / np.linalg.norm(wf), crit(wf), crit(np.array([1., 0])))     # [0. 1.]  4.0  0.0

Key lesson

PCA is label-blind (Bishop Fig. 12.7) — the same lesson as C3 Example 5.

Example 5 — Very Hard · PCA and whitening together

• Problem: A data set has 4 PCs with eigenvalues $(8,4,2,2)$. (a) How many components are needed for $\le 10\%$ reconstruction error? (b) After whitening all 4 components, what is the covariance and the new reconstruction error if the last two are dropped? (c) Why is whitening then PCA-truncation not equivalent to PCA-truncation?
• Asked: Three answers.
• Concept: Interaction of PCA and whitening.
• Approach: Cumulative variance; whitened eigenvalues are all $1$.
• Solution: (a) Total $16$; need retained $\ge 90\%=14.4$: $M=3$: $14$ ($87.5\%$, error $12.5\%$); $M=4$: $16$. So all $4$. (b) Whitened covariance $=I_4$; dropping two components loses $2/4=50\%$ of the (now equal) variance — error $=2$ (whitened units). (c) After whitening every direction has variance $1$, so no direction is more important by variance; truncation then discards directions arbitrarily, not those with least original variance. Whitening is for decorrelation / normalisation, not for compression.
• Final answer: (a) $4$ components; (b) $I_4$, error $2$ ($50\%$); (c) whitening removes the variance ranking.

Key lesson

Do dimensionality reduction before (or instead of) whitening.

Common mistakes

• Using PCA when the class-discriminative direction has small variance.
• Reporting PCA scores without keeping the mean and basis.

Exam traps

• PCA: unsupervised, uses only $\vec{X}$; Fisher: supervised, uses labels.
• Variance retained $={\sum }_{i\le M}{\lambda }_i/{\sum }_i{\lambda }_i$.

Connections: C3 (feature extraction), C44–C47, SVM / kNN preprocessing.

Mastery checklist

• Compute compression ratio, retained variance and error.
• Contrast PCA with Fisher using the criterion.
• Explain what whitening does and does not do.