\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

M03.6 · Low-rank approximation and PCA

A free, illustrated module of 4 lessons and one interactive in M03 Linear Algebra II: Decompositions: The best rank-k approximation; Image compression by rank; PCA from the covariance matrix; PCA by SVD, in practice.

M03.6 L2 · Intermediate 4 lessons · about 100 min Live · in review

Part of M03 Linear Algebra II: Decompositions in the Mathematics track.

Cut the singular value decomposition after k layers and you get the best rank-k copy of a matrix: no other matrix of that rank comes closer, and the error is exactly the singular values you dropped. These four lessons prove that, use it to compress a picture by rank, and then turn the same idea on data: principal component analysis finds the directions in which a cloud of points spreads most, first from the covariance matrix and then, as libraries do it, from the SVD of the centred data.

What you need first. The singular value decomposition and its rank-one layers (M03.5), the spectral theorem and the Rayleigh quotient of a symmetric matrix (M03.3), and covariance (M06.10). NumPy arrays (P02.1) are used in every code section.

Lessons

1. The best rank-k approximation M03.6.1 25 min

   Cut the singular value decomposition after k layers and you have the closest matrix of rank k. Derive the error, in the Frobenius and the spectral norm, from the singular values you dropped, and test the Eckart-Young theorem against random rivals.

2. Image compression by rank M03.6.2 25 min

   A greyscale picture is a matrix, so the truncated SVD compresses it. Count what k layers cost to store, watch how fast a photograph’s singular values fall, choose k by the share of the energy kept, and see why noise refuses to compress.

3. PCA from the covariance matrix M03.6.3 25 min

   Principal component analysis finds the directions in which a cloud of data spreads most. Centre the data, form the covariance matrix, and its eigenvectors are those directions; derive why, and why the same line makes the perpendicular gaps as small as possible.

4. PCA by SVD, in practice M03.6.4 25 min

   The SVD of the centred data gives the principal directions, their variances and the scores in one step, without forming the covariance matrix. Derive why, decide whether to standardise, choose how many components to keep, and run PCA on the iris measurements from scratch and with scikit-learn.

The interactive

M03.6-X1 · Rank slider. Rebuild a small picture from its first k layers as k runs from 1 to 48, watch the singular values being kept and dropped, and read off how many numbers are stored and how much of the energy is kept. It lives in Image compression by rank.