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).

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).

---

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

• 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=\frac{1}{2}(1+1)=1$; ${\vec{O}}_1^T{\vec{O}}_2=\frac{1}{2}(1-1)=0$.
• Final answer: Yes.
• Key lesson: Orthonormal = unit length + mutually perpendicular.

Example 2 — Easy

• 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.828\cdot \frac{1}{\sqrt{2}}(1,1)+1.414\cdot \frac{1}{\sqrt{2}}(1,-1)=(2,2)+(1,-1)=(3,1)$ ✓.
• Final answer: $(2.828,1.414)$.
• Key lesson: Coordinates are rotated components.

Example 3 — Moderate

• 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}}_1{\Vert }^2=\frac{1+4+4}{9}=1$, similarly for ${\vec{O}}_2,{\vec{O}}_3$. ${\vec{O}}_1^T{\vec{O}}_2=\frac{2+2-4}{9}=0$; ${\vec{O}}_1^T{\vec{O}}_3=\frac{2-4+2}{9}=0$; ${\vec{O}}_2^T{\vec{O}}_3=\frac{4-2-2}{9}=0$ ✓. ${\alpha }_1=\frac{3+12+0}{3}=5$; ${\alpha }_2=\frac{6+6}{3}=4$; ${\alpha }_3=\frac{6-12}{3}=-2$. Reconstruction: $5{\vec{O}}_1+4{\vec{O}}_2-2{\vec{O}}_3=\frac{1}{3}(5+8-4,10+4+4,10-8-2)=\frac{1}{3}(9,18,0)=(3,6,0)$ ✓. Parseval: $\Vert \vec{X}{\Vert }^2=9+36=45=25+16+4$ ✓.
• Final answer: $\alpha =(5,4,-2)$.
• Key lesson: Lengths are preserved by orthonormal coordinates.

Example 4 — Hard

• 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{1}{3}(5+8,10+4,10-8)=(\frac{13}{3},\frac{14}{3},\frac{2}{3})$. Residual $=\vec{X}-\hat{\vec{X}}=-2{\vec{O}}_3=\frac{1}{3}(-4,4,-2)$; $\Vert \cdot {\Vert }^2=\frac{16+16+4}{9}=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$.
• Key lesson: The error equals the sum of squares of the discarded coordinates — so discard the small ones.

Example 5 — Very Hard

• 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.

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 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

• 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 ⇒ axes are the PCs.

Example 2 — Easy

• 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$. For $\lambda =4$: $(S-4I)\vec{u}=0\Rightarrow \left(\begin{array}{cc}-1& 1\\ 1& -1\end{array}\right)\vec{u}=0\Rightarrow {\vec{u}}_1=\frac{1}{\sqrt{2}}(1,1)$. For $\lambda =2$: ${\vec{u}}_2=\frac{1}{\sqrt{2}}(1,-1)$. Variance along $(1,0)$: $(1,0)S(1,0{)}^T=3<4$.
• Final answer: $(4,\frac{1}{\sqrt{2}}(1,1))$, $(2,\frac{1}{\sqrt{2}}(1,-1))$; axis-aligned variance $3$.
• Key lesson: Correlation tilts the best direction off the axes.

Example 3 — Moderate

• Problem: Data $(-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}=\frac{1+1+1+1}{4}=1$; $S_{12}=\frac{2+1+1+2}{4}=1.5$. $\mathrm{tr}S=3.5$, $\det S=2.5-2.25=0.25$. $\lambda =\frac{3.5\pm \sqrt{12.25-1}}{2}=\frac{3.5\pm 3.3541}{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.
• Key lesson: A nearly 1-D cloud compresses almost losslessly.

Example 4 — Hard

• 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$: $5/10=50\%$; $M=2$: $8/10=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$.
• Key lesson: The Rayleigh quotient is bounded by the extreme eigenvalues.

Example 5 — Very Hard

• 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={\vec{u}}_1^T\vec{X}$: $-2.2271,-1.3764,1.3764,2.2271$; $z_2$: $0.2007,-0.3250,0.3250,-0.2007$. $\mathrm{Var}(z_1)=\frac{2(4.9602)+2(1.8945)}{4}=3.4273$ ✓ $={\lambda }_1$; $\mathrm{Var}(z_2)=\frac{2(0.0403)+2(0.1056)}{4}=0.0730$ ✓. $\mathrm{Cov}=\frac{1}{4}[(-2.2271)(0.2007)+(-1.3764)(-0.3250)+(1.3764)(0.3250)+(2.2271)(-0.2007)]=\frac{1}{4}[-0.4470+0.4473+0.4473-0.4470]\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$.
• Key lesson: PCA produces uncorrelated coordinates — this is why it is also called 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 (centred or not) 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

• 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 = discarded eigenvalues.

Example 2 — Easy

• 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$).
• Key lesson: The lecture notes that no principled automatic choice of $M$ exists — thresholds like this are a heuristic.

Example 3 — Moderate

• 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{1+1+0}{3}=\frac{2}{3}$; $S_{22}=\frac{1+1+4}{3}=2$; $S_{12}=\frac{(-1)(-1)+(1)(-1)+0}{3}=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 $y-2=-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

• 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) $(1,0)S(1,0{)}^T=3$. (b) $\frac{1}{2}(1,-1)S(1,-1{)}^T=\frac{1}{2}(3-1-1+3)=2$. (c) $\frac{1}{2}(1,1)S(1,1{)}^T=\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.
• Key lesson: $J\in [{\lambda }_{\min },{\lambda }_{\max }]$ for any one-direction discard.

Example 5 — Very Hard

• 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$ ($c_i={\vec{O}}^T{\vec{u}}_i$). ${\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=(-0.5257,0.8507)$: 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 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

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

Example 2 — Easy

• 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{1+1+0}{3}=\frac{2}{3}$; $S_{22}=\frac{1+1+4}{3}=2$; $S_{12}=\frac{1-1+0}{3}=0$.
• Final answer: $S=\mathrm{diag}(\frac{2}{3},2)$.
• Key lesson: Zero covariance ⇒ PCs are the coordinate axes.

Example 3 — Moderate

• 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=-2.2271(0.8507,0.5257)=(-1.8946,-1.1708)$. Error vector $=(-2,-1)-(-1.8946,-1.1708)=(-0.1054,0.1708)$; $\Vert e{\Vert }^2=0.0111+0.0292=0.0403$. Mean squared error over the four points $=\frac{0.0403+0.1056+0.1056+0.0403}{4}=0.0730={\lambda }_2$ ✓.
• Final answer: MSE $={\lambda }_2=0.073$.
• Key lesson: Algorithm and theory agree.

Example 4 — Hard

• Problem: Two features measured in different units: $A=(100,200,300)$ (e.g. grams), $B=(1,3,2)$ (e.g. 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}=\frac{10^4+0+10^4}{3}=6666.7$; $S_{BB}=\frac{1+1+0}{3}=0.6667$; $S_{AB}=\frac{(-100)(-1)+0+(100)(0)}{3}=33.33$. Raw: ${\lambda }_1\approx 6666.7$, ${\vec{u}}_1\approx (1,0.005)$ — essentially feature $A$ alone (units dominate). Standardised: ${\sigma }_A=81.65$, ${\sigma }_B=0.8165$; $\rho =\frac{33.33}{81.65\times 0.8165}=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)$.
• Key lesson: Standardise when features have different scales.

Example 5 — Very Hard

• 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$ ⇒ Cov$(\vec{y})={\Lambda }^{-1/2}\Lambda {\Lambda }^{-1/2}=I$ ✓. Point: $U^T\vec{x}=\frac{1}{\sqrt{2}}(2,2)=(1.4142,1.4142)$; ${\Lambda }^{-1/2}=\mathrm{diag}(\frac{1}{2},\frac{1}{\sqrt{2}})$ ⇒ $\vec{y}=(0.7071,1.0)$. Check variance along ${\vec{u}}_1$ direction after scaling: original variance $4$ ⇒ divided by $\sqrt{4}=2$.
• Final answer: $\vec{y}=(0.707,1.0)$; Cov$(\vec{y})=I$.
• Key lesson: Whitening = rotate to 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 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.

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

• 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$ eigenvalues equal $0$, $=D-N+1$).
• Key lesson: Centring costs one dimension.

Example 2 — Easy

• 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

• 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$. The other eigenvalues: $\det (G-\mu I)$ gives $\mu =2$ with $\vec{v}=\frac{1}{\sqrt{2}}(-1,1,0)$ [check: $G\vec{v}=\frac{1}{\sqrt{2}}(-2,2,0)=2\vec{v}$ ✓] and $\mu =6$ with $\vec{v}=\frac{1}{\sqrt{6}}(1,1,-2)$ [check: $G(1,1,-2{)}^T=(2+4,2+4,-2-2-8)=(6,6,-12)=6(1,1,-2{)}^T$ ✓]. Dividing by $N=3$: $\lambda =(2,\frac{2}{3},0)$.
• Final answer: $\lambda =2,\frac{2}{3},0$ (trace $\frac{8}{3}=\frac{8}{3}$ ✓).
• 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

• 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}}(1-1+0,0,1+1+4,0)=\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)$ [$X^{T}X$: col1·col1$=1+1+0=2$; col3·col3$=1+1+4=6$; col1·col3$=1-1+0=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}}(-1-1,0,-1+1,0)=\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}$.
• Key lesson: The two-step method reproduces the direct answer.

Example 5 — Very Hard

• 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\cdot 10^{12}=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.

Worked examples

Example 1 — Very Easy

• 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

• 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

• 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

• 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)$ (variance $\approx 100$ vs $\approx 2$ along $y$). Fisher: ${\vec{m}}_2-{\vec{m}}_1=(0,2)$; $S_W^{-1}=\mathrm{diag}(0.01,1)$ ⇒ ${\vec{w}}_F\propto (0,2)\to (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$).
• Key lesson: PCA is label-blind (Bishop Fig. 12.7).

Example 5 — Very Hard

• Problem: Combine ideas: 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=2$: $12$ ($75\%$); $M=3$: $14$ ($87.5\%$); $M=4$: $16$. So all $4$ components (error $\le 10\%$ only at $M=4$; $M=3$ gives $12.5\%$). (b) Whitened covariance $=I_4$; dropping two components loses $2/4=50\%$ of the (now equal) variance — error $=2$ (in 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/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.