Home / MLF / Week 6

Week 6 · SVD and PCA: squeezing data

Official syllabus line: Linear Algebra - Singular value decomposition, Principal Component Analysis in Image Processing

About 90 minQuiz 2 material (see exam radar)BSCS2004 · Harish Guruprasad Ramaswamy, Arun Rajkumar, Prashanth LA

Before you start: Weeks 3, 4 and 5 (projection, eigenvectors, symmetric matrices).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine kneading dough. You turn it, stretch it long in one direction, then turn it again. This simple three-step recipe is exactly how complex data transformations work! We call this amazing process Singular Value Decomposition, or SVD. It helps us understand how any matrix changes space.
SVD helps us find the most important 'stretches' in data. Like a photo: most information is in the biggest stretches. Discarding smaller stretches makes a smaller file, still looking great! PCA uses this for data points: finding the view that shows maximum spread, using SVD's powerful idea.
Let’s look at three data points like beads on a string. First, we center them around the middle. Then, using PCA, we find the best line through them. This line shows 100 percent of their spread, meaning all their movement is perfectly captured by just one direction!
For exams, remember to center data for PCA and carefully calculate covariance. SVD helps you understand matrix ranks and compression. PCA finds the best data views. Master these concepts to unlock the secrets of data and matrices. You've got this! Keep practicing!

The one-minute story

Think of it like this

Knead a ball of dough: you turn it, stretch it along one direction, then turn it again. Any matrix, however messy, acts on space exactly like that: a turn, a stretch along the coordinate axes, and another turn. This three-step recipe is the singular value decomposition (SVD). The stretch amounts are called singular values, and the big ones tell you where the "action" of the matrix lives.

Now think of a photograph, which is just a big table of brightness numbers (a matrix). Most of its information sits in the first few stretch amounts; the rest is fine detail you would hardly miss. Throw the small ones away and you get a smaller file that still looks almost identical. That is image compression.

PCA (principal component analysis) uses the same idea on a cloud of data points: "Which flat view of this cloud shows the most spread?" You will find the answer is the SVD (or the eigenvectors of the covariance matrix) of the data.

By the end of this week you can:

state the SVD $A=U\Sigma V^T$ and compute singular values from $A^TA$ ;
connect rank with the number of non-zero singular values;
build the best low-rank approximation and count how much storage it saves;
compute a covariance matrix and run PCA by hand on small data;
compute variance explained and reconstruction error.

Words you need

Singular values $\sigma_1\ge\sigma_2\ge\dots\ge0$ - the stretch amounts of the SVD. Never negative.
Singular vectors - the columns of $V$ (input directions) and $U$ (output directions).
Low-rank approximation - replacing a matrix by a simpler one that uses only its biggest singular values.
Centering - subtracting the average from each feature so the data cloud is centred at the origin.
Covariance matrix - a table of how every pair of features moves together; the diagonal holds the variances.
Principal component - a direction along which the data is spread out the most.
Variance explained - the share of the total spread captured by the chosen directions.

Idea 1: The singular value decomposition

The idea

Every matrix $A$ (any shape, any rank) can be written

A=U\,\Sigma\,V^T

$V$ is an $n\times n$ orthogonal matrix (the first turn),
$\Sigma$ is an $m\times n$ matrix that is zero except for the non-negative numbers $\sigma_1\ge\sigma_2\ge\dots$ on its diagonal (the stretch),
$U$ is an $m\times m$ orthogonal matrix (the final turn).

How to get them:

singular values $\sigma_i=\sqrt{\text{eigenvalues of }A^TA}$ ;
right singular vectors (columns of $V$ ) are the eigenvectors of $A^TA$ ;
left singular vectors (columns of $U$ ) are the eigenvectors of $AA^T$ , with $\mathbf u_i=A\mathbf v_i/\sigma_i$ .

$A^TA$ is symmetric and positive semi-definite (week 5), so its eigenvalues are real and $\ge0$ , which is why the square roots make sense.

Rank: the rank of $A$ equals the number of non-zero singular values.

Writing it out term by term:

A=\sigma_1\mathbf u_1\mathbf v_1^T+\sigma_2\mathbf u_2\mathbf v_2^T+\cdots+\sigma_r\mathbf u_r\mathbf v_r^T

Each term is a rank-1 piece, and they are listed from biggest to smallest.

Solved example: 1. SVD of a rank-1 matrix

Question. Find the singular values of $A=\begin{pmatrix}1&2\\2&4\end{pmatrix}$ and write $A$ as $\sigma\,\mathbf u\mathbf v^T$ .

Solution.

$A^TA=\begin{pmatrix}5&10\\10&20\end{pmatrix}$ . Trace $25$ , determinant $100-100=0$ . Eigenvalues $25$ and $0$ .
Singular values: $\sigma_1=\sqrt{25}=5$ and $\sigma_2=0$ . Only one is non-zero, so $\operatorname{rank}A=1$ (indeed the second column is twice the first).
Eigenvector of $A^TA$ for $25$ : $(1,2)/\sqrt5$ , so $\mathbf v_1=\frac1{\sqrt5}(1,2)$ .
$\mathbf u_1=A\mathbf v_1/\sigma_1=\frac{1}{5}\cdot\frac1{\sqrt5}(5,10)=\frac1{\sqrt5}(1,2)$ .
So $A=5\cdot\frac1{\sqrt5}\binom12\cdot\frac1{\sqrt5}(1\;2)=\begin{pmatrix}1&2\\2&4\end{pmatrix}$ . ✓

Watch out - real exam trap

Singular values are not eigenvalues. For $B=\begin{pmatrix}3&0\\0&-2\end{pmatrix}$ the eigenvalues are $3$ and $-2$ , but the singular values are $3$ and $2$ , because singular values can never be negative and come from $B^TB=\operatorname{diag}(9,4)$ . They coincide with eigenvalues only for symmetric positive semi-definite matrices. Exam options love "singular values are the eigenvalues of $A$ ".

Facts that appear as true/false statements

SVD exists for every matrix, square or not.
$\sigma_i\ge0$ always. The largest, $\sigma_1$ , is the biggest amount $A$ can stretch a unit vector: $\|A\|_2=\sigma_1$ .
$A$ is $m\times n$ of rank $r$ $\Rightarrow$ exactly $r$ non-zero singular values (and $\min(m,n)-r$ zero ones).
A $10\times8$ matrix of rank $8$ has $8$ non-zero singular values, so $A^TA$ ( $8\times8$ ) is invertible. That is exactly the condition for a unique least-squares solution (week 3).

Low-rank approximation and image compression

Eckart-Young theorem: among all matrices of rank $k$ , the closest one to $A$ is obtained by keeping only the first $k$ terms of the sum above. The error is made only of the discarded singular values: $\|A-A_k\|_F^2=\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots$ .

Solved example: 2. How much does compression save?

Question. A grey-scale image is a $100\times100$ matrix. You keep only its top $5$ singular values. How many numbers must you store, compared with the original?

Solution. The original needs $100\times100=10{,}000$ numbers. The rank-5 version $\sum_{i=1}^5\sigma_i\mathbf u_i\mathbf v_i^T$ needs, for each $i$ , one $\sigma_i$ , one $100$ -long $\mathbf u_i$ and one $100$ -long $\mathbf v_i$ : $5\times(100+100+1)=1005$ numbers. About 10 % of the storage, and for a typical photo the picture is still recognisable.

Idea 2: PCA, finding the best view of a data cloud

Say you have $n$ data points, each with $d$ features, stored as the columns of a $d\times n$ matrix $X$ .

Step 1: Centre. Subtract the mean of each feature, so the cloud is centred at the origin. (Skip this and PCA is wrong: the first "component" would just point at the average.)

Step 2: Covariance matrix.

C=\frac1n\sum_{i=1}^n\mathbf x_i\mathbf x_i^T=\frac1nXX^T

The diagonal entries $C_{jj}$ are the variances of each feature, and $C_{jk}$ measures how features $j$ and $k$ rise and fall together. $C$ is symmetric and positive semi-definite.

Step 3: Eigen-analysis. The principal components are the eigenvectors of $C$ , ordered by eigenvalue. The eigenvalue $\lambda_k$ is the variance of the data along component $k$ .

Why? The spread of the data along a unit direction $\mathbf u$ is $\frac1n\sum(\mathbf u^T\mathbf x_i)^2=\mathbf u^TC\mathbf u$ . We want the $\mathbf u$ with $\|\mathbf u\|=1$ that makes this as big as possible. Week 9's Lagrange multipliers will show the answer satisfies $C\mathbf u=\lambda\mathbf u$ and the value reached is $\lambda$ . The biggest spread is the top eigenvalue and its eigenvector.

Two ways to say what PCA does

Maximise the spread (variance) of the shadows on the chosen axes.
Minimise the reconstruction error: the squared distance between each point and its shadow.

Since each point satisfies $\|\mathbf x\|^2=\|\text{shadow}\|^2+\|\text{leftover}\|^2$ (Pythagoras), these are the same problem. The animation shows it: the total never changes, so as shadow-spread rises, the loss falls.

The idea

With eigenvalues $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_d$ of $C$ :

variance explained by the top $k$ components $=\dfrac{\lambda_1+\dots+\lambda_k}{\lambda_1+\dots+\lambda_d}$
reconstruction error (average squared) when keeping $k$ components $=\lambda_{k+1}+\dots+\lambda_d$ (the discarded eigenvalues)
projecting $\mathbf x$ onto the top $k$ components $W=[\mathbf w_1\cdots\mathbf w_k]$ : coordinates $W^T\mathbf x$ , reconstruction $WW^T\mathbf x$ (a projection matrix, week 3)

The link to SVD. If $X=U\Sigma V^T$ is the SVD of the centred data matrix, then $C=\frac1nXX^T=U\frac{\Sigma^2}{n}U^T$ . So the principal components are the left singular vectors $\mathbf u_i$ , and $\lambda_i=\sigma_i^2/n$ . PCA and SVD are two names for one computation.

Solved example: 3. Covariance and PCA on points that sit on a line

Question. The data points are $(1,2),\,(3,4),\,(5,6)$ . Find $C$ , the principal components and the variance explained by the first.

Solution.

Means: $\bar x=3$ , $\bar y=4$ . Centred points: $(-2,-2),\,(0,0),\,(2,2)$ .
$\sum x^2=4+0+4=8$ , $\sum xy=4+0+4=8$ , $\sum y^2=8$ . With $n=3$ : $C=\dfrac13\begin{pmatrix}8&8\\8&8\end{pmatrix}=\begin{pmatrix}\frac83&\frac83\\\frac83&\frac83\end{pmatrix}$ .
Trace $=\frac{16}3$ , determinant $=0$ , so eigenvalues $\frac{16}3$ and $0$ .
PC1 $=\frac1{\sqrt2}(1,1)$ , the direction of the line. PC2 $=\frac1{\sqrt2}(1,-1)$ .
Variance explained by PC1 $=\frac{16/3}{16/3}=100\%$ . Reconstruction error with one component $=0$ : the points lie exactly on a line, so one number per point loses nothing.

The covariance entry $8/3$ is a number you will see again and again in past papers.

Solved example: 4. Variance explained, projection and reconstruction

Question. A data set has covariance matrix $C=\begin{pmatrix}3&1\\1&3\end{pmatrix}$ . (a) Find the principal components. (b) What fraction of the variance does PC1 explain? (c) Project the centred point $\mathbf x=(2,4)$ onto PC1 and reconstruct it. (d) What is the variance along the direction $\mathbf u=(1,0)$ ?

Solution.

Trace 6, determinant $9-1=8$ : $\lambda^2-6\lambda+8=0$ , so $\lambda=4,\,2$ . Eigenvectors: $(1,1)/\sqrt2$ for $4$ and $(1,-1)/\sqrt2$ for $2$ .
(b) $\dfrac{4}{4+2}=\dfrac23\approx66.7\%$ .
(c) Coordinate on PC1: $\frac{1}{\sqrt2}(2+4)=\frac6{\sqrt2}\approx4.24$ . Reconstruction: $4.24\cdot\frac1{\sqrt2}(1,1)=(3,3)$ . Error vector $(2,4)-(3,3)=(-1,1)$ , squared length $2$ (which equals the squared coordinate on PC2, $(\frac{2-4}{\sqrt2})^2=2$ ).
(d) Variance along any unit direction $\mathbf u$ is $\mathbf u^TC\mathbf u$ . For $\mathbf u=(1,0)$ that is just $C_{11}=3$ . For $\mathbf u=\frac1{\sqrt2}(1,1)$ : $\frac12(3+1+1+3)=4$ , the maximum, as expected.

True statements about PCA (the exam's favourite MSQ)

It is unsupervised (no labels used).
Components are orthogonal (eigenvectors of a symmetric matrix) and the projected features are uncorrelated.
Variance explained by a component is its eigenvalue divided by the sum of all eigenvalues.
You must centre the data; if features have different units you should also scale them.
With $n$ points and $d$ features there are at most $\min(n,d)$ useful components (centering removes one more: rank of the centred data is at most $n-1$ ).
PCA is not linear regression: regression measures vertical errors to predict $y$ ; PCA measures perpendicular distances and treats all features alike.

Your turn

Your turn: 1. Singular values

$M^TM=\begin{pmatrix}9&0\\0&4\end{pmatrix}$ for some matrix $M$ . What are the singular values of $M$ , and what is the sum of the singular values?

Need a hint?

$\sigma_i=\sqrt{\text{eigenvalue of }M^TM}$ .

Show the full solution

Eigenvalues $9,\,4$ give $\sigma=3,\,2$ ; the sum is $5$ . (The trap option "singular values equal the eigenvalues of $M$ " is not generally true.)

Your turn: 2. Rank from singular values

$A$ is $10\times8$ with singular values $7,\,5,\,5,\,2,\,1,\,1,\,0.5,\,0.1$ . What is its rank, and is $A^TA$ invertible?

Need a hint?

Count the non-zero singular values.

Show the full solution

All 8 are non-zero, so rank $=8$ and $A^TA$ ( $8\times8$ ) has rank 8, so it is invertible: least squares has a unique solution.

Your turn: 3. Compression ratio

A $200\times300$ image is approximated with its top $10$ singular values. How many numbers are stored, and what fraction of the original?

Need a hint?

Each rank-1 piece needs one $\sigma$ , one $\mathbf u$ (length 200) and one $\mathbf v$ (length 300).

Show the full solution

$10\times(200+300+1)=5010$ numbers. The original has $60{,}000$ . So about $8.4\%$ .

Your turn: 4. Covariance by hand

Points $(1,0),\,(-1,0),\,(0,2),\,(0,-2)$ (already centred). Find $C$ , its eigenvalues, and the variance explained by PC1.

Need a hint?

Sum $x^2$ , $xy$ , $y^2$ and divide by $n=4$ .

Show the full solution

$\sum x^2=1+1+0+0=2$ , $\sum xy=0$ , $\sum y^2=0+0+4+4=8$ . $C=\begin{pmatrix}0.5&0\\0&2\end{pmatrix}$ , already diagonal, so eigenvalues $2$ and $0.5$ . PC1 $=(0,1)$ (the $y$ -axis). Variance explained $=\frac{2}{2.5}=80\%$ .

Your turn: 5. Projected variance

For $C=\begin{pmatrix}5&2\\2&2\end{pmatrix}$ , what is the variance of the data when projected on the unit vector $\mathbf u=\frac1{\sqrt5}(2,1)$ ?

Need a hint?

Compute $\mathbf u^TC\mathbf u$ .

Show the full solution

$C\mathbf u=\frac1{\sqrt5}(10+2,\;4+2)=\frac1{\sqrt5}(12,6)$ . Then $\mathbf u^TC\mathbf u=\frac15(2\cdot12+1\cdot6)=\frac{30}5=\mathbf 6$ . (In fact $(2,1)$ is an eigenvector with eigenvalue 6: it is PC1.)

Exam radar

MLF Quiz 2: (of the 30 Quiz 2 papers that have a concept summary) SVD in all 30, PCA in 29, covariance matrix in 23, eigenvalues of the covariance matrix in 7, projection onto principal components in 3. In the End Term, "which is true about PCA" (an MSQ) appears about 22 times, covariance of given points about 11 times, and projected-variance computations about 9 times; SVD true/false MSQs another 6.

Reliable question types: compute $C$ from 3 to 4 points (watch the $1/n$ ), eigenvalues of a $2\times2$ covariance matrix, " $\sigma$ from $A^TA$ ", "rank of a $10\times8$ matrix", and "which statements about PCA are true".

Watch out - real exam trap

Divide by $n$ (or $n-1$ ) when forming $C$ , according to what the question says. In this course papers use $\frac1nXX^T$ .
Reconstruction error = the sum of the discarded eigenvalues, not the kept ones.
Singular values $\ne$ eigenvalues of $A$ .
Forgetting to centre the data before computing $C$ .
Principal components are eigenvectors of the covariance matrix, not of the raw data matrix.

Quick quiz

A matrix has singular values 6, 3 and 0. Its rank is...

The rank equals the number of non-zero singular values: two.

The principal components of centred data are...

the rows of the data matrix
the eigenvectors of the covariance matrix
the singular values
the mean vector

They are the eigenvectors of the covariance matrix, equivalently the left singular vectors of the centred data matrix.

The covariance matrix has eigenvalues 5, 3 and 2. Keeping the first component, the variance explained is...

50 percent
30 percent
20 percent
100 percent

5 / (5+3+2) = 0.5.

Select all that are TRUE about PCA. (select all that apply)

It is an unsupervised method.
The principal components are mutually orthogonal.
The data does not need to be centred.
Reconstruction error equals the sum of the kept eigenvalues.

Centering is needed, and the reconstruction error is the sum of the discarded eigenvalues.

Recap

Remember this

SVD: $A=U\Sigma V^T$ for any matrix. $\sigma_i=\sqrt{\text{eig}(A^TA)}\ge0$ . Rank = number of non-zero $\sigma_i$ .
Best rank- $k$ approximation: keep the top $k$ terms; storage $k(m+n+1)$ .
PCA: centre $\to$ covariance $C=\frac1nXX^T$ $\to$ eigenvectors = components, eigenvalues = variances.
Variance explained $=\sum_{\text{kept}}\lambda/\sum\lambda$ ; reconstruction error $=\sum_{\text{discarded}}\lambda$ .
PCA = SVD of the centred data, $\lambda_i=\sigma_i^2/n$ .

Formulas to keep

$A=U\Sigma V^T=\sum_i\sigma_i\mathbf u_i\mathbf v_i^T$ ; $\sigma_i=\sqrt{\lambda_i(A^TA)}$ ; $\text{rank}A=\#\{\sigma_i\ne0\}$
Rank- $k$ storage: $k(m+n+1)$ ; error $\|A-A_k\|_F^2=\sum_{i>k}\sigma_i^2$
Covariance (centred): $C=\frac1nXX^T$ ; variance along unit $\mathbf u$ : $\mathbf u^TC\mathbf u$
Variance explained: $\frac{\sum_{i\le k}\lambda_i}{\sum_i\lambda_i}$ ; reconstruction error: $\sum_{i>k}\lambda_i$
$\lambda_i(C)=\sigma_i^2/n$

Connected weeks (learn them together)

MLT week 1 - PCA: finding the best view of your data: SVD is the machinery under PCA.
MLP week 12 - Unsupervised learning in sklearn: PCA in sklearn is an SVD behind the scenes.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 28 real questions on this week All Quiz 2 papers