Unit 12 · Principal Component Analysis — The Math Behind the Machine

1

Pick the better line

Imagine this

Your cousin wants a photo of his new cricket bat for his WhatsApp status.

Hold the bat side-on and the photo shows everything: the long blade, the handle, how wide it is. Now point the camera straight down the handle. The photo shows a small dark rectangle. You cannot even tell it is a bat.

Same bat. Same camera. The only thing you changed is the direction you looked from.

A cloud of data points works the same way. From some directions it looks spread out, and you can tell the points apart. From others it collapses into a blob. Try it on a cloud shaped like a bat.

Try: press end-on — the photo shrinks to a blob and keeps only about 5% of the spread. Then press side-on: over 99%. Now press ▶ and watch the number rise and fall as the camera walks around the bat.

drag the picture to orbit

turn90°

tilt0°

—

Now make it smaller. Here are five points: $(1,2),\ (4,5),\ (7,8),\ (8,4),\ (10,6)$ . Say you are allowed to keep only one number per point. Which number should it be?

Option 1: keep only the first number. You get $1,\,4,\,7,\,8,\,10$ . Their average is $6$ . The distances from the average are $-5,\,-2,\,1,\,2,\,4$ . Square them and take the average: $(25+4+1+4+16)/5=10$ .

That number, the average squared distance from the middle, is how we measure spread. Its proper name is the variance.

Option 2: keep only the second number. You get $2,\,5,\,8,\,4,\,6$ , and the spread is only $4$ .

Option 3: a slanted line that goes 2 steps right for every 1 step up. Drop each point onto it and read where it lands. The spread comes out to $12$ . That beats both axes.

So the best single number is not one of the columns you were given. It is a mix of them, read along a slanted line. Finding that line is the whole job of this unit.

Here is the same game with 90 points. Each point drops onto the line along a grey thread, the shortest way. That drop is called projecting the point onto the line.

Try: drag the orange tip round, or press ▶ sweep. Watch the marker ride the hump below: it peaks at $\lambda_1$ and dips to $\lambda_2$ exactly a quarter-turn later. Then switch to the five points and find the angle where the spread is $12$ .

drag the orange tip to turn the line

angle120°

The realization

Look at the cloud from every direction. For each one, drop the points onto the line and measure how spread out they land. Keep the direction with the biggest spread.

That is principal component analysis (PCA). Everything else in this unit is the machinery that does this search quickly, and the reason it works. On the 90 points, line A has spread $5.45$ and line B only $0.41$ . You have just done PCA by eye.

Pause & predict

On line B the 90 dots crowd into a short stretch. What goes wrong if you describe each point only by where it lands on B?

Pause & predict

Sweep the line through every angle and the spread traces one smooth hump. How far apart are the best angle and the worst angle?

Here is the path through this unit, one step at a time:

①Why spread is the information — a column that never changes can never explain anything.
②Centre, then build one small table — the covariance matrix $C$ holds every spread you will need.
③One score per direction — the spread along any direction $\mathbf w$ is $\mathbf w^\top C\mathbf w$ .
④The leash — fix the length of $\mathbf w$ and the best directions turn out to be eigenvectors.
⑤The multiplier is the spread — the eigenvalue tells you how much spread each direction keeps.
⑥The second, the third, the rest — and a fixed budget that says how many to keep.
⑦Three more views of one answer — smallest rebuild error, columns that never repeat each other, and the SVD.
⑧PCA in the real world — finding eigenvectors by just multiplying, data wider than it is tall, the recipe, the traps, and one example done start to finish.

In one sentence: PCA looks at a cloud of data from every direction and keeps the direction along which the points land most spread out.

2

Why spread is the information

Imagine this

A chai stall owner wants to know why he sells 300 cups on some days and only 80 on others. So every evening he writes down a few things: the temperature, whether it rained, the day of the week — and the colour of his kettle.

The kettle is the same steel kettle every single day. Can it explain why sales go up and down?

Of course not. Something that never changes cannot explain something that changes.

Every model you will ever build has the same skeleton. Something you want to predict, $y$ , is driven by your inputs $\mathbf x$ , plus some noise $\varepsilon$ for everything you did not measure:

y=f(\mathbf x)+\varepsilon

A straight line, a decision tree and a neural network are all just different choices of $f$ .

Now read that line as a statement about change. If $y$ moves, it moved because $\mathbf x$ moved, or because of the noise. So for every input column, the useful question is simple: how much does this column change? The tool that measures change is the one you met in §1 — the variance.

Here is a small example. We want to predict salaries from four columns: age, years of experience, number of certifications and number of trainings. Their variances are:

column	variance	what it means
age	$64$	changes a lot from person to person
experience	$41$	changes a lot too
certifications	$0.09$	almost everyone has zero
trainings	$0.04$	almost everyone has zero

The last two columns hardly move. Like the steel kettle, they cannot explain why one salary is higher than another. Dropping them costs almost nothing.

That leaves age and experience. These two have a different problem: they are twins. Older people usually have more experience, so the two columns mostly say the same thing. A normal feature-selection method would delete one twin. PCA does something smarter. It builds one new direction that carries what both were saying, and a second direction, at right angles, that carries the little that is left.

The one surprising move

Look at what PCA was given: only the four columns. It never sees a single salary. As Prof. Saurabh puts it in class: "PCA doesn't get bothered by what you have in y. It only takes your x input features."

That is its strength — you can rank directions before you ever look at the target. It is also its main weakness, and §14 shows a case where it bites.

Because PCA swaps $D$ old columns for $M$ new ones, people describe it with three different names. All three are right:

People call it	because	compared with the usual way
dimension reduction	$D$ columns go in, fewer ( $M$ ) come out	the plain description of what happens
feature selection	you choose which directions survive	the usual way needs a model first, then feature importance, then a cut; PCA chooses before any model exists
feature engineering	each new column is a fresh mix $z_1=a_1x_1+\dots+a_Dx_D$	like building "loan ÷ income" by hand, except PCA finds the weights for you

And you get a bonus for free: the new columns never repeat each other. §10 shows why.

The realization

A model can only explain change in $y$ using change in $\mathbf x$ . So a direction along which the data barely changes carries almost no information, whatever the target is.

That is why PCA ranks directions by their spread — and why it can do so without ever looking at $y$ .

Pause & predict

A fifth column is added: "works in the Pune office". Every employee in this data works in Pune, so the column is the same for everyone. How much of the difference in salaries can it explain?

In one sentence: a column that barely changes cannot explain anything, so PCA ranks directions by their spread, and it does this without ever looking at the thing you want to predict.

3

Centre first, then build one small table

Imagine this

A PT teacher measures every child's height from the floor: 142 cm, 150 cm, 138 cm, 146 cm. Every number is big, and most of each number is just the distance up from the floor.

Now she measures from the class average instead: $-2$ , $+6$ , $-6$ , $+2$ . Suddenly every number tells you something: who is taller than usual, and by how much.

Measuring from the average is called centring. PCA always does it first.

Take the five points from §1 again: $(1,2),\ (4,5),\ (7,8),\ (8,4),\ (10,6)$ .

Step 1: find the middle. The average of the first numbers is $30/5=6$ . The average of the second numbers is $25/5=5$ . So the middle of the cloud is $(6,5)$ .

Step 2: subtract the middle from every point. Write the answers as the rows of a table. That table is the centred data matrix $X$ : one row per point ( $N=5$ rows), one column per feature ( $D=2$ columns).

X=\begin{bmatrix}-5&-3\\ -2&0\\ 1&3\\ 2&-1\\ 4&1\end{bmatrix}

Quick check: each column now adds up to zero. $-5-2+1+2+4=0$ and $-3+0+3-1+1=0$ . The cloud now sits around the origin.

Step 3: build one small table. For every pair of columns, multiply them row by row, add up, and divide by the number of points.

column 1 with itself: $(25+4+1+4+16)/5=50/5=10$
column 2 with itself: $(9+0+9+1+1)/5=20/5=4$
column 1 with column 2: $(15+0+3-2+4)/5=20/5=4$

Put the three numbers in a square:

C=\frac1N X^\top X=\begin{bmatrix}10&4\\ 4&4\end{bmatrix}

This is the covariance matrix. Read it like this:

The diagonal holds each column's own spread: $10$ for the first column, $4$ for the second. These are exactly the numbers you found in §1.
The off-diagonal number says how much the two columns move together. It is positive here, so when a point is to the right of the middle, it also tends to be above it.
$C$ is symmetric: "column 1 with column 2" is the same as "column 2 with column 1".

Two details that cost marks

Divide by $N$ , not $N-1$ . Here $N=5$ , so we divide by $5$ . Many software packages divide by $N-1=4$ by default, which gives $\begin{bmatrix}12.5&5\\5&5\end{bmatrix}$ — the same directions, but different numbers. This course divides by $N$ .

Centre first. The formula $\tfrac1N X^\top X$ is the covariance only when every column averages to zero. Skip the centring and you get a different matrix with different eigenvectors.

Try: drag the top-right point up and right, and watch the off-diagonal entry grow as the cloud tilts. Then switch to forgot to centre and see every entry jump — and the ellipse's long axis swing toward the mean.

drag the points

The realization

$C=\frac1N X^\top X$

After centring, one small $D\times D$ table says how much each column moves (the diagonal) and which columns move together (the rest). From here on, $C$ is the only thing about the data that PCA will ever use.

Pause & predict

For the five centred points, which covariance matrix does this course use?

Pause & predict

You forget to centre and compute $\tfrac15 X^\top X$ on the raw points $(1,2),\dots,(10,6)$ . You get $\begin{bmatrix}46&34\\34&29\end{bmatrix}$ . What is wrong with it?

If you want the algebra · 2 proofs, step by step

Prove it · what each entry of C measures

Claim. For centred data $X$ ( $N\times D$ , rows $\mathbf x_i$ ), the entry $C_{jk}$ of $C=\tfrac1N X^\top X$ is $\tfrac1N\sum_i x_{ij}x_{ik}$ : the variance of column $j$ when $j=k$ , and the covariance of columns $j$ and $k$ otherwise. $C$ is symmetric.

1

Entry

(j,k)

of

X^\top X

is row

j

of

X^\top

times column

k

of

X

. Row

j

of

X^\top

is column

j

of

X

. So

(X^\top X)_{jk}=\sum_{i=1}^N x_{ij}\,x_{ik}.

"Multiply the two columns row by row and add" — the recipe used on the five points.

2

Each column has mean

0

, so

x_{ij}

is already "distance from the mean". Hence

C_{jj}=\tfrac1N\sum_i x_{ij}^2

is the average squared distance from the mean — the variance of column

j

— and

C_{jk}=\tfrac1N\sum_i x_{ij}x_{ik}

is the covariance of columns

j

and

k

. A product

x_{ij}x_{ik}

is positive when both columns are on the same side of their means, negative when they are on opposite sides. The average says which usually happens.

3

Swapping

j

and

k

does not change

\sum_i x_{ij}x_{ik}

, so

C_{jk}=C_{kj}

:

C^\top=C

. ∎ Symmetry is what later guarantees real eigenvalues and perpendicular eigenvectors (Unit 4's spectral theorem).

Prove it · forgetting to centre adds the mean

Claim. If $\tilde X$ holds the raw (uncentred) points with mean $\boldsymbol\mu$ , then $\tfrac1N\tilde X^\top\tilde X=C+\boldsymbol\mu\boldsymbol\mu^\top$ . For the five points this is $\begin{bmatrix}10&4\\4&4\end{bmatrix}+\begin{bmatrix}36&30\\30&25\end{bmatrix}=\begin{bmatrix}46&34\\34&29\end{bmatrix}$ .

1

Write each raw point as mean plus deviation,

\tilde{\mathbf x}_i=\boldsymbol\mu+\mathbf x_i

, where the deviations

\mathbf x_i

add up to

\mathbf 0

. Then

\begin{aligned}&\frac1N\sum_i\tilde{\mathbf x}_i\tilde{\mathbf x}_i^\top\\ &=\frac1N\sum_i(\boldsymbol\mu+\mathbf x_i)(\boldsymbol\mu+\mathbf x_i)^\top\\ &=\boldsymbol\mu\boldsymbol\mu^\top+\boldsymbol\mu\bar{\mathbf x}^\top+\bar{\mathbf x}\boldsymbol\mu^\top\\ &\quad+\frac1N\sum_i\mathbf x_i\mathbf x_i^\top,\end{aligned}

where

\bar{\mathbf x}=\tfrac1N\sum_i\mathbf x_i

is the mean of the deviations.

\tfrac1N X^\top X

is the same as

\tfrac1N\sum_i\mathbf x_i\mathbf x_i^\top

: a sum of one small table per point.

2

The deviations add up to zero, so

\bar{\mathbf x}=\mathbf 0

and the two middle terms vanish. The last term is

C

. So the raw table is

C+\boldsymbol\mu\boldsymbol\mu^\top

. ∎ The extra piece

\boldsymbol\mu\boldsymbol\mu^\top

points along the mean. That is why the uncentred matrix's top direction swings toward

(6,5)

— it is describing where the cloud sits, not how it spreads.

In one sentence: subtract the average from every column, then one small symmetric table $C=\tfrac1N X^\top X$ records how much each column moves and which columns move together.

4

Every direction gets one score

Imagine this

Your tailor takes your measurements once and writes them in a small notebook. After that, you never need to stand in his shop again. He can tell how any new kurta design will fit you — straight from the notebook.

$C$ is the data's notebook. Once you have it, you can work out the spread along any direction without touching the data again.

Pick a direction and write it as an arrow of length 1, $\mathbf w$ . Each centred point $\mathbf x_i$ lands on the line at $z_i=\mathbf x_i^\top\mathbf w$ — one dot product per point. All of them together are $\mathbf z=X\mathbf w$ .

The landing spots average to zero, because the data is centred. So their spread is just the average of their squares. Watch the data disappear:

\begin{aligned}\text{spread of }\mathbf z&=\frac1N\,\mathbf z^\top\mathbf z=\frac1N\,(X\mathbf w)^\top(X\mathbf w)\\ &=\mathbf w^\top\Big(\frac1N X^\top X\Big)\mathbf w=\mathbf w^\top C\,\mathbf w.\end{aligned}

The left side talks about the projected points. The right side has only $C$ and $\mathbf w$ . The data has vanished into $C$ .

Try it on the five points, with $C=\begin{bmatrix}10&4\\4&4\end{bmatrix}$ :

$\mathbf w=(1,0)$ : $\ \mathbf w^\top C\mathbf w=10$ . The spread of the first column, as in §1.
$\mathbf w=(0,1)$ : $\ \mathbf w^\top C\mathbf w=4$ . The second column.
$\mathbf w=\tfrac1{\sqrt5}(2,1)$ : $\ \mathbf w^\top C\mathbf w=\tfrac15(40+8+8+4)=12$ . The slanted line from §1.

The same three numbers as in §1. This time, not one data point was touched.

So every direction gets one score. You can picture all the scores at once as a surface: over each arrow $(w_1,w_2)$ , stand a height $\mathbf w^\top C\mathbf w$ . It is a bowl. The directions of length 1 form a ring on the floor, and the ring lifted onto the bowl is a wavy rim. Its highest point is the best direction.

Try: press ▶ and ride the marker around the ring. It climbs to $12$ and drops to $2$ , twice each lap, because $\mathbf w$ and $-\mathbf w$ are the same line. Switch to $\begin{bmatrix}5&4\\4&5\end{bmatrix}$ : the high points swing to $45^\circ$ .

drag the picture to orbit

direction45°

—

The height at an arrow of length 1 is the spread of the data along it. Only the ring matters: inside it the arrows are too short, outside too long.

The realization

$\text{spread along }\mathbf w=\mathbf w^\top C\,\mathbf w$

For any arrow $\mathbf w$ of length 1: one number for every direction, and no data needed. PCA is now a clean question: which unit arrow $\mathbf w$ makes $\mathbf w^\top C\mathbf w$ as big as possible?

Pause & predict

With $C=\begin{bmatrix}10&4\\4&4\end{bmatrix}$ , what is the spread along the 45° direction $\mathbf w=\tfrac1{\sqrt2}(1,1)$ ?

If you want the algebra · 1 proof, step by step

Prove it · the spread along w is wᵀCw

Claim. For centred data $X$ and a unit vector $\mathbf w$ , the landing positions $z_i=\mathbf x_i^\top\mathbf w$ have mean $0$ and variance $\mathbf w^\top C\mathbf w$ .

1

The mean of the

z_i

is

\tfrac1N\sum_i\mathbf x_i^\top\mathbf w=\big(\tfrac1N\sum_i\mathbf x_i\big)^\top\mathbf w=\mathbf 0^\top\mathbf w=0

. Projection is linear, so the projected mean is the projection of the mean — and the mean is

\mathbf 0

.

2

With mean

0

, the variance is the average square. Stack the

z_i

as

\mathbf z=X\mathbf w

:

\operatorname{Var}(z)=\frac1N\sum_i z_i^2=\frac1N\,\mathbf z^\top\mathbf z.

A sum of squares is a dot product of a vector with itself.

3

Substitute and regroup, using

(AB)^\top=B^\top A^\top

:

\begin{aligned}&\frac1N(X\mathbf w)^\top(X\mathbf w)\\ &=\frac1N\,\mathbf w^\top X^\top X\,\mathbf w\\ &=\mathbf w^\top\Big(\frac1N X^\top X\Big)\mathbf w=\mathbf w^\top C\,\mathbf w.\end{aligned}

∎ The data is gone — only

C

is left. This is also why

C

can never have a negative eigenvalue:

\mathbf w^\top C\mathbf w

is an average of squares, so it is never below

0

.

In one sentence: the spread along any unit direction $\mathbf w$ is $\mathbf w^\top C\mathbf w$ , so once you have $C$ every direction gets a score without looking at the data again.

5

The leash — why the arrow must have length one

Imagine this

School sports day. The rule: "whoever throws the ball farthest wins". One boy quietly walks ten metres past the line before he throws. Of course he wins.

But he did not throw better. He changed the rules. For a fair contest, everyone has to throw from the same line.

Our contest has the same loophole. Take the winning direction from §4, $\mathbf w=\tfrac1{\sqrt5}(2,1)$ , with spread $12$ . Now double the arrow to $2\mathbf w$ . Every landing number $z_i$ doubles, so every square grows four times, and the "spread" jumps to $48$ . Triple it and you get $108$ .

The arrow did not point anywhere better. It just got longer. We care about the direction, not the length.

So we put the arrow on a leash of length 1. The length of an arrow is $\|\mathbf w\|=\sqrt{\mathbf w^\top\mathbf w}$ , so "length 1" is the same as $\mathbf w^\top\mathbf w=1$ . Now the question is fair:

\max_{\mathbf w}\ \mathbf w^\top C\,\mathbf w\qquad\text{subject to}\qquad \mathbf w^\top\mathbf w=1.

Make something as big as possible, while obeying a rule. You met exactly this in Unit 11: there was a wall, and we turned the wall into a fine. Do the same here. Write the rule as "something $=0$ ", namely $\mathbf w^\top\mathbf w-1=0$ , and charge a fine $\lambda$ for breaking it:

L(\mathbf w,\lambda)=\mathbf w^\top C\,\mathbf w-\lambda\,(\mathbf w^\top\mathbf w-1).

At the best point, the slope of $L$ with respect to $\mathbf w$ is zero. The slope of $\mathbf w^\top C\mathbf w$ is $2C\mathbf w$ , and the slope of $\mathbf w^\top\mathbf w$ is $2\mathbf w$ . So

2C\mathbf w-2\lambda\mathbf w=\mathbf 0\qquad\Longrightarrow\qquad C\mathbf w=\lambda\,\mathbf w.

Stop and look at that. We asked a question about spread, and the answer came back as the definition of an eigenvector (Unit 4): an arrow that $C$ only stretches, never turns. The best direction must be an eigenvector of $C$ . Nothing else is even a candidate.

Why the fine works — the picture

The leash lets $\mathbf w$ walk only on the unit circle. Stand at the best point on the circle. If a tiny step along the circle made the score go up, you would take it — so at the top, a step along the circle changes nothing.

That means the uphill arrow of the score, $\nabla f=2C\mathbf w$ , has no part along the circle. It must point straight out of the circle. And "straight out of the circle" is the direction of $\mathbf w$ itself — the uphill arrow of the rule, $\nabla g=2\mathbf w$ . Two arrows pointing the same way: $\nabla f=\lambda\nabla g$ , which is $C\mathbf w=\lambda\mathbf w$ again.

Try: drag the bead around the circle and watch the parallel meter. The two arrows line up — angle $0^\circ$ — at exactly two kinds of place: the top of the score (PC1) and the bottom (PC2). Everywhere else the orange arrow leans along the circle, telling you which way is uphill.

drag the bead along the circle

bead at70°

The realization

$C\mathbf w=\lambda\,\mathbf w$

On the leash, the best direction is the place where the uphill arrow $2C\mathbf w$ points straight along $\mathbf w$ . That is exactly what an eigenvector is. The directions PCA is looking for are the eigenvectors of $C$ .

Pause & predict

Why can't we simply maximise $\mathbf w^\top C\mathbf w$ with no leash at all?

Pause & predict

You slide $\mathbf w$ around the unit circle. At the best point, which way does the uphill arrow $2C\mathbf w$ point?

If you want the algebra · 2 proofs, step by step

Prove it · the fine turns into Cw = λw

Claim. Any $\mathbf w$ that maximises $\mathbf w^\top C\mathbf w$ subject to $\mathbf w^\top\mathbf w=1$ satisfies $C\mathbf w=\lambda\mathbf w$ for some number $\lambda$ .

1

For a symmetric matrix

A

, the gradient of

q(\mathbf w)=\mathbf w^\top A\mathbf w

is

2A\mathbf w

. Write

q=\sum_{j,k}A_{jk}w_jw_k

and differentiate by

w_m

:

\begin{aligned}\frac{\partial q}{\partial w_m}&=\sum_k A_{mk}w_k+\sum_j A_{jm}w_j\\ &=2\,(A\mathbf w)_m.\end{aligned}

w_m

appears once as

w_j

and once as

w_k

; symmetry

A_{jm}=A_{mj}

makes the two sums equal. With

A=I

this gives

\nabla(\mathbf w^\top\mathbf w)=2\mathbf w

.

2

The Lagrangian is

L(\mathbf w,\lambda)=\mathbf w^\top C\mathbf w-\lambda(\mathbf w^\top\mathbf w-1)

. Setting both partial derivatives to zero:

\begin{gathered}\frac{\partial L}{\partial\mathbf w}=2C\mathbf w-2\lambda\mathbf w=\mathbf 0,\\ \frac{\partial L}{\partial\lambda}=-(\mathbf w^\top\mathbf w-1)=0.\end{gathered}

The second equation just gives the leash back. The first is the new information.

3

Divide the first by

2

:

C\mathbf w=\lambda\mathbf w

, with

\mathbf w\ne\mathbf 0

because it has length 1. So

\mathbf w

is an eigenvector of

C

and

\lambda

its eigenvalue. ∎ The slides write the fine with the opposite sign,

L=\mathbf b^\top S\mathbf b+\lambda(1-\mathbf b^\top\mathbf b)

. It is the same function, so the same answer.

Prove it · why the two arrows must line up

Claim. If $\mathbf w^\star$ maximises $f(\mathbf w)$ on the curve $g(\mathbf w)=c$ , and $\nabla g(\mathbf w^\star)\ne\mathbf 0$ , then $\nabla f(\mathbf w^\star)=\lambda\,\nabla g(\mathbf w^\star)$ for some $\lambda$ .

1

Take a tiny step

\boldsymbol\delta

that stays on the curve. Then

g

does not change, so to first order

\nabla g\cdot\boldsymbol\delta=0

: the step is at right angles to

\nabla g

. On the unit circle,

\nabla g=2\mathbf w

points straight out, and every step along the circle is at right angles to it.

2

At the best point, that step cannot change

f

either: if

\nabla f\cdot\boldsymbol\delta>0

you would step forward, and if it were

<0

you would step backward, and

f

would go up. So

\nabla f\cdot\boldsymbol\delta=0

as well. This is the "you would take it" argument from the page, written as one line.

3

In two dimensions the steps along the curve form one line, and both

\nabla f

and

\nabla g

are at right angles to it. Two arrows at right angles to the same line are parallel:

\nabla f=\lambda\nabla g

. (In more dimensions the same holds, because both are at right angles to every allowed step.) With

f=\mathbf w^\top C\mathbf w

,

g=\mathbf w^\top\mathbf w

:

2C\mathbf w=2\lambda\mathbf w

. ∎ The Lagrangian is just bookkeeping for this picture:

\partial L/\partial\mathbf w=\mathbf 0

is "the arrows line up", and

\partial L/\partial\lambda=0

is "stay on the curve".

In one sentence: fix the arrow's length to 1, turn that rule into a fine, and setting the slope to zero leaves $C\mathbf w=\lambda\mathbf w$ — the best directions are eigenvectors of $C$ .

6

The fine turns out to be the spread

Imagine this

The commentator says, "the required run rate is 9". That one number means three things at once. It is runs per over. It is how fast the score must climb. And it is the slope of the worm chart.

Three readings, one number. The $\lambda$ in PCA is like that.

We know the best direction is an eigenvector. But $C$ has several. Which one wins? Put $C\mathbf w=\lambda\mathbf w$ back into the score:

\mathbf w^\top C\mathbf w=\mathbf w^\top(\lambda\mathbf w)=\lambda\,\mathbf w^\top\mathbf w=\lambda\cdot1=\lambda.

The spread along an eigenvector is its eigenvalue. So the winner is simple: the eigenvector with the largest eigenvalue.

Check it on $C=\begin{bmatrix}5&4\\4&5\end{bmatrix}$ with $\mathbf w=\tfrac1{\sqrt2}(1,1)$ . Then $C\mathbf w=\tfrac1{\sqrt2}(9,9)=9\,\mathbf w$ , so $\lambda=9$ . And $\mathbf w^\top C\mathbf w=\tfrac12(5+4+4+5)=9$ . The other eigenvector, $\tfrac1{\sqrt2}(1,-1)$ , has $\lambda=1$ and spread $1$ . No direction does better than $9$ , and none does worse than $1$ .

So the same number $\lambda$ plays three parts:

Read it as	it is	where you see it
the fine (Lagrange multiplier)	the price of the rule $\\|\mathbf w\\|=1$	$L=\mathbf w^\top C\mathbf w-\lambda(\mathbf w^\top\mathbf w-1)$
an eigenvalue	how much $C$ stretches $\mathbf w$	$C\mathbf w=\lambda\mathbf w$
a variance	the spread of the data along $\mathbf w$	$\mathbf w^\top C\mathbf w=\lambda$

Keep the two roles apart. The principal component is the eigenvector $\mathbf w$ — a direction. The eigenvalue $\lambda$ is the spread along it — a number.

Try: press snap to PC1. The orange arrow $C\mathbf w$ lies exactly on top of $\mathbf w$ , the landing dots spread as wide as they can, and all three panels read $\lambda_1$ . Now turn $\mathbf w$ a little: the three numbers split apart.

arrow w at20°

The realization

$\mathbf w^\top C\mathbf w=\lambda$

The spread along an eigenvector is its eigenvalue. So the largest spread is the largest eigenvalue, and it lives along that eigenvector. The same number is the stretch, the spread and the fine. That is why we always list eigenvalues from biggest to smallest, $\lambda_1\ge\lambda_2\ge\dots$ : it is a ranking of directions by how much of the data they show.

Pause & predict

For $C=\begin{bmatrix}5&4\\4&5\end{bmatrix}$ , what is the largest spread you can get along any unit direction?

Pause & predict

For $C=\begin{bmatrix}5&2\\2&8\end{bmatrix}$ the top eigenvalue is $9$ , with eigenvector direction $(1,2)$ . A student forgets to shrink it to length 1 and computes the spread along $(1,2)$ itself. What does she get?

If you want the algebra · 1 proof, step by step

Prove it · spread = λ, and nothing beats λ₁

Claim. (a) If $C\mathbf w=\lambda\mathbf w$ , then $\mathbf w^\top C\mathbf w=\lambda\|\mathbf w\|^2$ , which is $\lambda$ for a unit vector. (b) For every unit $\mathbf w$ , $\lambda_D\le\mathbf w^\top C\mathbf w\le\lambda_1$ .

1

(a)

\mathbf w^\top C\mathbf w=\mathbf w^\top(\lambda\mathbf w)=\lambda\,\mathbf w^\top\mathbf w=\lambda\|\mathbf w\|^2

. So the unit length is not optional: for

(1,2)

with

\lambda=9

the "spread" is

9\times5=45

.

2

(b) Write any unit

\mathbf w

in the orthonormal eigenvectors:

\mathbf w=c_1\mathbf w_1+\dots+c_D\mathbf w_D

, with

c_1^2+\dots+c_D^2=1

. Then

\mathbf w^\top C\mathbf w=\sum_d\lambda_d\,c_d^2.

The cross terms vanish because the eigenvectors are at right angles:

\mathbf w_j^\top C\mathbf w_k=\lambda_k\mathbf w_j^\top\mathbf w_k=0

for

j\ne k

.

3

That is a weighted average of the

\lambda_d

with weights

c_d^2

adding to

1

. An average can never exceed the largest value or fall below the smallest:

\begin{aligned}\lambda_D=\lambda_D\sum_d c_d^2&\le\sum_d\lambda_d c_d^2\\ &\le\lambda_1\sum_d c_d^2=\lambda_1.\end{aligned}

The top is reached only when all the weight sits on

\mathbf w_1

. ∎ This is the hump from §1 in one line: every direction's spread is a blend of the eigenvalues, and the blend is biggest when it is pure

\lambda_1

.

In one sentence: put $C\mathbf w=\lambda\mathbf w$ back into the score and it becomes $\lambda$ , so the fine, the stretch and the spread are one number, and the top eigenvector wins.

7

The second direction, and all the rest

Imagine this

You give an auto driver directions: "Go straight down MG Road for 3 km." That covers most of the trip.

Then: "Now turn left, 400 metres." The second instruction only helps because it goes a new way. Telling him "go straight another 400 m" would just repeat the first instruction.

The first component gets the biggest share of the spread. The second one should get the biggest share of what is left — without repeating the first. There are two ways to say this, and they give the same answer.

Route A — add a second leash. Ask for the best unit direction $\mathbf w_2$ that is also at right angles to the first: $\mathbf w_2^\top\mathbf w_1=0$ . That is one more rule, so one more fine, $\mu$ :

L=\mathbf w_2^\top C\mathbf w_2-\lambda(\mathbf w_2^\top\mathbf w_2-1)-\mu\,\mathbf w_2^\top\mathbf w_1.

Set the slope to zero, then multiply by $\mathbf w_1^\top$ . Almost every term dies, and you are left with $\mu=0$ . The second fine is free! So the condition is again $C\mathbf w_2=\lambda\mathbf w_2$ : the second component is also an eigenvector, the one with the second-largest eigenvalue.

Route B — peel off what you already have. This is the way the slides do it. Take the part of every point that lies along $\mathbf w_1$ , and remove it:

\hat X=X-X\mathbf w_1\mathbf w_1^\top.

(The slides store points as columns, so they write $\hat X=X-\mathbf b_1\mathbf b_1^\top X$ . Same thing.) The cloud is squashed flat along $\mathbf w_1$ . Now find the top direction of this cloud. Its covariance $\hat C$ has the same eigenvectors as $C$ , except that $\mathbf w_1$ 's eigenvalue has dropped to $0$ . So the new winner is $\mathbf w_2$ . Peel again to get $\mathbf w_3$ , and so on.

	Route A · second leash	Route B · peel it off
the idea	best direction at right angles to the ones you have	best direction of what the old ones did not explain
what you solve	$C\mathbf w_2=\lambda\mathbf w_2$ , after showing $\mu=0$	the top eigenvector of $\hat C$
the answer	$\mathbf w_2$ , with spread $\lambda_2$	$\mathbf w_2$ , with spread $\lambda_2$

One more gift. We never had to force the components to be at right angles. $C$ is symmetric, and Unit 4's spectral theorem says a symmetric matrix always has a full set of eigenvectors that are all at right angles to each other. Perpendicular comes free. Its eigenvalues are also real and never negative — they are spreads, after all.

Try: press the buttons in order. After the first peel the orange bar falls to $0$ and the other two do not move at all — then the top of what is left is exactly the second direction. Or press ▶ and watch the whole story.

drag the picture to orbit

The realization

$\begin{gathered}C\mathbf w_d=\lambda_d\mathbf w_d\\ \lambda_1\ge\lambda_2\ge\dots\ge\lambda_D\ge0\end{gathered}$

Each new component is the best direction of what is left. Whether you add a leash or peel off the old components, you land on the next eigenvector of the same $C$ — and they all meet at right angles for free.

Pause & predict

A 3-D cloud has eigenvalues $9,\ 4,\ 1$ . You peel off the first component. What are the eigenvalues of what is left?

If you want the algebra · 2 proofs, step by step

Prove it · the second fine is free (μ = 0)

Claim. Maximising $\mathbf w_2^\top C\mathbf w_2$ subject to $\mathbf w_2^\top\mathbf w_2=1$ and $\mathbf w_2^\top\mathbf w_1=0$ , where $C\mathbf w_1=\lambda_1\mathbf w_1$ , gives $C\mathbf w_2=\lambda\mathbf w_2$ .

1

Two rules, two fines:

L=\mathbf w_2^\top C\mathbf w_2-\lambda(\mathbf w_2^\top\mathbf w_2-1)-\mu\,\mathbf w_2^\top\mathbf w_1

. Setting the gradient to zero:

2C\mathbf w_2-2\lambda\mathbf w_2-\mu\mathbf w_1=\mathbf 0.

The gradient of

\mathbf w_2^\top\mathbf w_1

with respect to

\mathbf w_2

is just

\mathbf w_1

.

2

Multiply on the left by

\mathbf w_1^\top

, and use

\mathbf w_1^\top C=(C\mathbf w_1)^\top=\lambda_1\mathbf w_1^\top

. The three terms become

2\lambda_1(\mathbf w_1^\top\mathbf w_2)

,

2\lambda(\mathbf w_1^\top\mathbf w_2)

and

\mu(\mathbf w_1^\top\mathbf w_1)

, and

\mathbf w_1^\top\mathbf w_2=0

,

\mathbf w_1^\top\mathbf w_1=1

:

0-0-\mu\cdot1=0\ \Longrightarrow\ \mu=0.

C

is symmetric, so

\mathbf w_1^\top C

is the transpose of

C\mathbf w_1

.

3

With

\mu=0

, step 1 reads

C\mathbf w_2=\lambda\mathbf w_2

. Among eigenvectors at right angles to

\mathbf w_1

, the spread

\lambda

is biggest for

\lambda_2

. Repeat for

\mathbf w_3

with two right-angle rules, and so on. ∎ The right-angle rule costs nothing because the best free answer already obeys it: eigenvectors of a symmetric matrix are perpendicular anyway.

Prove it · peeling keeps the eigenvectors (both cases)

Claim. Let $B=\mathbf w_1\mathbf w_1^\top+\dots+\mathbf w_{m-1}\mathbf w_{m-1}^\top$ (the flattener onto the used directions) and $\hat X=X-XB$ . Then $\hat C=\tfrac1N\hat X^\top\hat X=(I-B)C(I-B)$ has every eigenvector $\mathbf w_i$ of $C$ : with eigenvalue $0$ if $i\le m-1$ , and with the same $\lambda_i$ if $i\ge m$ .

1

B

is symmetric and

\hat X=X(I-B)

, so

\begin{aligned}\hat C&=\frac1N(I-B)^\top X^\top X(I-B)\\ &=(I-B)\,C\,(I-B)\\ &=C-CB-BC+BCB.\end{aligned}

This is the slides' expansion

S-SB-BS+BSB

, in our row layout.

2

Case $i\ge m$ (not yet used).

\mathbf w_i

is at right angles to every used direction, so

B\mathbf w_i=\mathbf 0

. Also

BC\mathbf w_i=\lambda_iB\mathbf w_i=\mathbf 0

. Hence

\hat C\mathbf w_i=C\mathbf w_i=\lambda_i\mathbf w_i

(the other three terms are

\mathbf 0

). Untouched directions keep exactly their spread.

3

Case $i\le m-1$ (already used). Now

B\mathbf w_i=\mathbf w_i

, so

(I-B)\mathbf w_i=\mathbf 0

, and therefore

\hat C\mathbf w_i=(I-B)\,C\,(I-B)\mathbf w_i=\mathbf 0,

because the last factor

(I-B)\mathbf w_i

is already

\mathbf 0

. So the used directions are still eigenvectors, now with eigenvalue

0

. The largest eigenvalue of

\hat C

is therefore

\lambda_m

, with eigenvector

\mathbf w_m

. ∎ So peeling never invents a new direction. It just switches off the ones you have, and the next eigenvector of the original

C

moves to the top.

In one sentence: every later component is the top eigenvector of what the earlier ones left behind, and because $C$ is symmetric they all come out at right angles.

8

The spread budget is fixed

Imagine this

A family has ₹50,000 a month. They can move money between rent, groceries and school fees however they like. But no amount of moving creates one extra rupee.

PCA does the same with spread. Turning the axes moves spread between directions. It never creates it and never destroys it.

For the five points, the total spread in the original columns is $10+4=14$ — the sum of the diagonal of $C$ , called the trace. Along the two principal directions the spreads are $\lambda_1=12$ and $\lambda_2=2$ . And $12+2=14$ . The same budget, split differently.

This always holds, for any number of columns:

\operatorname{tr}(C)=C_{11}+C_{22}+\dots+C_{DD}=\lambda_1+\lambda_2+\dots+\lambda_D.

So each eigenvalue is a slice of one fixed budget, and its share is easy:

\text{share kept by the top }M=\frac{\lambda_1+\dots+\lambda_M}{\lambda_1+\dots+\lambda_D}.

For the five points, one component keeps $12/14=85.71\%$ of the spread. Plot every eigenvalue as a bar, biggest first, and you have a scree plot (scree is the pile of stones at the foot of a cliff — the bars fall like one). Plot the running total and you get the curve people actually decide from.

How many components $M$ should you keep? People use three rules:

rule	how it works	good for	watch out
hit a target share	keep adding components until the running total passes 90 %, 95 % or 99 %	the most common choice; easy to defend	you must pick the target
find the elbow	stop where the scree stops falling steeply and flattens out	a long, flat tail of noise	some plots have no clear elbow
keep $\lambda>1$ (Kaiser)	keep a component only if it carries more than one original column's worth	standardised data, where every column contributes exactly 1	meaningless if the columns were not standardised

A big percentage is not always good news

"PC1 explains 98 %" can mean the data really lies near a line. It can also mean one column is measured in units that make its numbers huge — say, salary in rupees next to age in years — and it simply dominates the total. Check that you standardised (§14) before you celebrate.

Try: on the practice-set eigenvalues, move the target to $90\%$ : the third bar lights up, because two components only reach $82.5\%$ . Then open the noisy tail and compare the three rules — they do not agree, and that is normal.

target share90 %

The realization

$\operatorname{tr}(C)=\lambda_1+\lambda_2+\dots+\lambda_D$

Turning the axes never changes the total spread. PCA just pushes as much of it as possible into the first few directions — which is exactly why keeping only those few loses so little.

Pause & predict

A five-column dataset has eigenvalues $4.5,\ 2.1,\ 0.9,\ 0.4,\ 0.1$ . What is the total spread, and what share do the first two keep?

Pause & predict

Same eigenvalues. What is the smallest number of components that keeps at least $90\%$ ?

If you want the algebra · 1 proof, step by step

Prove it · the trace is the sum of the eigenvalues

Claim. $\operatorname{tr}(C)=\sum_d C_{dd}=\sum_d\lambda_d$ : the total spread of the original columns equals the total spread along the principal directions.

1

The spectral theorem gives

C=W\Lambda W^\top

with

W^\top W=I

(all

D

eigenvectors as columns). Symmetric

C

always has a full set of perpendicular unit eigenvectors.

2

The trace does not change when you move the first factor of a product to the end:

\operatorname{tr}(AB)=\operatorname{tr}(BA)

. So

\begin{aligned}\operatorname{tr}(C)&=\operatorname{tr}\big(W\,\Lambda W^\top\big)\\ &=\operatorname{tr}\big(\Lambda W^\top W\big)\\ &=\operatorname{tr}(\Lambda)=\sum_d\lambda_d.\end{aligned}

∎ Why

\operatorname{tr}(AB)=\operatorname{tr}(BA)

: both are

\sum_{j,k}A_{jk}B_{kj}

— the same terms added in a different order.

In one sentence: the eigenvalues add up to the trace, so they split one fixed spread budget, and you keep the biggest slices until you have the share you need.

9

The second view — the smallest rebuild error

Imagine this

You text a friend where a dhaba is, using just one number: "7.2 km along the highway from the toll plaza". Your friend drives 7.2 km and stops on the highway.

If the dhaba is actually 300 m off the road, those 300 m are lost. They never fitted into your one number. That gap is the rebuild error.

If you get to choose the road, pick the one the dhabas hug most closely.

So far PCA has been about keeping the most spread. Here is the same thing seen from the other side: losing the least.

With the kept directions as the columns of $W$ , a point is squeezed into a short code and then rebuilt:

\begin{aligned}\text{encode:}\quad&\mathbf z=W^\top\mathbf x\quad\text{(one number per kept direction)}\\ \text{decode:}\quad&\tilde{\mathbf x}=W\mathbf z=WW^\top\mathbf x\quad\text{(back to a point on the line)}\end{aligned}

With one direction $\mathbf w$ , the rebuilt point $\tilde{\mathbf x}$ is the foot of the thread from $\mathbf x$ to the line. The point, the foot and the origin make a right-angled triangle. Pythagoras says:

\|\mathbf x\|^2=\underbrace{(\mathbf x^\top\mathbf w)^2}_{\text{kept}}+\underbrace{\|\mathbf x-\tilde{\mathbf x}\|^2}_{\text{lost}}.

Add this up over all the points. The left side is the total spread — fixed, whatever line you choose. So whatever you gain in "kept", you lose in "lost". It is a seesaw. The line that keeps the most spread is exactly the line that loses the least.

And the average loss has a clean value: it is the sum of the eigenvalues you dropped. For the five points, keeping one direction loses on average $\lambda_2=2$ per point.

One point, all the way through

A new point arrives: $(12,9)$ . Use the five points' mean $(6,5)$ and their top direction $\mathbf w_1=\tfrac1{\sqrt5}(2,1)$ .

Centre it: $(12-6,\ 9-5)=(6,4)$ .
Encode: $z=\mathbf w_1^\top(6,4)=\tfrac{12+4}{\sqrt5}=\tfrac{16}{\sqrt5}\approx7.155$ .
Decode: $z\,\mathbf w_1=\tfrac{16}{5}(2,1)=(6.4,\ 3.2)$ . Add the mean back: $\tilde{\mathbf x}=(12.4,\ 8.2)$ .
The error: $(6-6.4)^2+(4-3.2)^2=0.16+0.64=0.80$ .

And here is the neat part. Along the direction we threw away, $\mathbf w_2=\tfrac1{\sqrt5}(1,-2)$ , the point's score is $z_2=\tfrac{6-8}{\sqrt5}$ , and $z_2^2=\tfrac45=0.80$ . The error is exactly the squared score along the dropped direction.

Two products that look alike

$W^\top W=I$ : a small $M\times M$ table. It just says the kept directions have length 1 and meet at right angles.

$WW^\top$ is the big $D\times D$ one, and it is the flattener. It squashes any point onto the kept line (or plane). It equals $I$ only if you keep every direction. Whatever it squashes away is the rebuild error.

Try: turn the line slowly. The red part of the bar grows exactly as the blue part shrinks — the total never moves. The lost part is smallest precisely where the kept part is biggest. Then open the 3-D tab and tilt a glass plane through a 3-D cloud.

drag the orange tip to turn the line

angle100°

drag the picture to orbit

turn plane120°

tilt plane45°

The realization

$\begin{gathered}\text{lost}=\text{total}-\text{kept}\\ \frac1N\sum_i\|\mathbf x_i-\tilde{\mathbf x}_i\|^2=\lambda_{M+1}+\dots+\lambda_D\end{gathered}$

Because the total is fixed, "keep the most spread" and "lose the least" are one instruction. The slides call these the maximum-variance view and the projection view of PCA. They are two sides of one seesaw.

Pause & predict

The new point $(12,9)$ was rebuilt from one number as $(12.4,\ 8.2)$ . Its squared error is $0.80$ . Why is that the same as $z_2^2$ , the square of its score along $\mathbf w_2$ ?

Pause & predict

For the five points ( $\lambda_1=12,\ \lambda_2=2$ ) you keep one component. What is the average squared rebuild error over the five points?

If you want the algebra · 1 proof, step by step

Prove it · the average error is the dropped eigenvalues

Claim. With orthonormal kept directions $W$ ( $D\times M$ ) and $\tilde{\mathbf x}=WW^\top\mathbf x$ : $\|\mathbf x-\tilde{\mathbf x}\|^2=\|\mathbf x\|^2-\|W^\top\mathbf x\|^2$ , and averaged over the centred data $\tfrac1N\sum_i\|\mathbf x_i-\tilde{\mathbf x}_i\|^2=\operatorname{tr}(C)-\operatorname{tr}(W^\top CW)$ . With $W$ = the top $M$ eigenvectors this is $\lambda_{M+1}+\dots+\lambda_D$ , the smallest possible.

1

Expand the square, using

W^\top W=I

:

\begin{aligned}&\|\mathbf x-WW^\top\mathbf x\|^2\\ &=\mathbf x^\top\mathbf x-2\,\mathbf x^\top WW^\top\mathbf x\\ &\quad+\mathbf x^\top W(W^\top W)W^\top\mathbf x\\ &=\|\mathbf x\|^2-\|W^\top\mathbf x\|^2.\end{aligned}

For one direction: error

=\|\mathbf x\|^2-(\mathbf x^\top\mathbf w)^2

— Pythagoras, in symbols.

2

Average over the points.

\tfrac1N\sum_i\|\mathbf x_i\|^2=\operatorname{tr}(C)

, and

\tfrac1N\sum_i\|W^\top\mathbf x_i\|^2=\operatorname{tr}(W^\top CW)

, the total spread kept. So average error

=

total

-

kept. The total does not depend on

W

. Minimising the error and maximising the kept spread are the same problem — the seesaw.

3

With

W=[\mathbf w_1\cdots\mathbf w_M]

,

W^\top CW=\operatorname{diag}(\lambda_1,\dots,\lambda_M)

, so the kept spread is

\lambda_1+\dots+\lambda_M

and the average error is

\lambda_{M+1}+\dots+\lambda_D

. Choosing the top eigenvectors keeps the most, so it loses the least. ∎ Five points,

M=1

: the error is

\lambda_2=2

on average; the new point

(12,9)

happens to lose

0.80

.

In one sentence: by Pythagoras, what a direction keeps plus what it loses always adds up to the same total, so the line with the most spread is also the line with the smallest rebuild error.

10

New columns that never repeat each other

Imagine this

Two friends rush in with the same news, at the same moment, in almost the same words. From the second one you learn nothing new.

Age and experience are like those two friends: when one goes up, the other usually does too. PCA swaps them for new columns that never echo each other.

The new columns are the scores $Z=XW$ : one column per kept direction. What does their covariance look like? Do the same three-line move as §4:

\begin{aligned}\operatorname{Cov}(Z)&=\frac1N Z^\top Z=W^\top\Big(\frac1N X^\top X\Big)W\\ &=W^\top C\,W=\Lambda=\begin{bmatrix}\lambda_1&&\\&\ddots&\\&&\lambda_M\end{bmatrix}.\end{aligned}

The last step uses $CW=W\Lambda$ (all the eigen-equations side by side) and $W^\top W=I$ .

Everything off the diagonal is zero. Off-diagonal entries are how much two columns move together — so the new columns are uncorrelated. And each new column's spread is its eigenvalue: "spread $=\lambda$ " once more, for all components at once.

This is why PCA is popular before a regression. Correlated inputs make a model unsure which twin is doing the work. The usual fix deletes one twin and throws information away. PCA keeps all the information but re-expresses it along directions that never overlap.

Reading a component: the loadings

"But then I no longer know what my columns mean!" Not quite. Each component is a recipe:

z_1=a_1x_1+a_2x_2+\dots+a_Dx_D,\qquad \mathbf w_1=(a_1,\dots,a_D).

The weights $a_d$ are called the loadings. They are just the entries of the eigenvector. Say three columns — age, experience, certifications — give

\mathbf w_1=\tfrac17(6,\,3,\,2)\approx(0.86,\ 0.43,\ 0.29),\qquad \mathbf w_2=\tfrac1{\sqrt5}(-1,\,2,\,0)\approx(-0.45,\ 0.89,\ 0).

Age has the biggest weight in $\mathbf w_1$ , so PC1 is "mostly an age axis". Experience leads $\mathbf w_2$ , so PC2 is "mostly an experience axis". The meaning is still there; you just read it one level deeper.

Any real set of loadings must pass two checks:

Length 1: $\tfrac1{49}(36+9+4)=1$ and $\tfrac15(1+4+0)=1$ . ✓
Right angles: $\mathbf w_1^\top\mathbf w_2=\tfrac1{7\sqrt5}(-6+6+0)=0$ . ✓

If a proposed pair fails either check, it is not a pair of principal components.

One more thing: the sign of a component means nothing. If $C\mathbf w=\lambda\mathbf w$ , then also $C(-\mathbf w)=\lambda(-\mathbf w)$ . Two programs may hand you opposite signs for the same data. Read the pattern — which loadings are big, which have the same sign — not whether one is $+0.7$ or $-0.7$ .

Try: press ▶ rotate and watch the correlation fall from $0.78$ to $0.00$ as the cloud turns to lie along the axes. On the loadings tab, press flip the signs: every bar changes sign, and nothing about the meaning changes.

turn0 %

drag the picture to orbit

The realization

$\operatorname{Cov}(Z)=W^\top C\,W=\Lambda$

The new columns are uncorrelated by construction, and each one's spread is its eigenvalue. The loadings are the recipe for each new column: read the pattern, not the sign.

Pause & predict

Someone hands you three proposed pairs of loadings for two columns. Which pair could really be the two principal components?

If you want the algebra · 1 proof, step by step

Prove it · the scores are uncorrelated

Claim. The scores $Z=XW$ , with $W$ holding unit eigenvectors of $C$ as columns, have mean $\mathbf 0$ and covariance $\operatorname{Cov}(Z)=\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_M)$ .

1

Each score column averages to zero, because

X

does (§4, step 1). So its covariance is

\tfrac1N Z^\top Z

:

\begin{aligned}\frac1N Z^\top Z&=\frac1N W^\top X^\top XW\\ &=W^\top CW.\end{aligned}

The same three-line move as

\mathbf w^\top C\mathbf w

, with a whole matrix of directions at once.

2

All eigen-equations side by side read

CW=W\Lambda

. And

W^\top W=I

. So

W^\top CW=W^\top W\Lambda=\Lambda.

∎ Off-diagonal zeros: no two components move together. Diagonal: each component's spread is its eigenvalue. For the five-eigenvalue example,

\operatorname{Cov}(Z)=\operatorname{diag}(4.5,\,2.1,\,0.9,\,0.4,\,0.1)

.

In one sentence: the scores have covariance $W^\top CW=\Lambda$ , so the new columns never repeat each other, and the loadings are the recipe that says what each one is made of.

11

Turn, stretch, turn — the SVD route

Imagine this

When you send a photo on WhatsApp, it is squeezed so it travels fast. Squeeze it a little and nobody notices. Squeeze it too hard and faces turn to blocks.

A photo is just a big table of numbers — a matrix. The best possible way to squeeze a matrix turns out to be PCA again, in a different coat.

Unit 5 showed that every matrix, however messy, does three simple things in a row: turn, stretch, turn. That is the singular value decomposition (SVD):

X=U\,\Sigma\,V^\top.

$U$ and $V$ are pure turns (their columns have length 1 and meet at right angles), and $\Sigma$ is a diagonal stretch with the singular values $\sigma_1\ge\sigma_2\ge\dots\ge0$ .

Now feed the SVD into the covariance matrix. The inner $U^\top U$ is $I$ , so it drops out:

\begin{aligned}C=\frac1N X^\top X&=\frac1N\,V\Sigma\,U^\top U\,\Sigma V^\top\\ &=V\,\frac{\Sigma^2}{N}\,V^\top.\end{aligned}

Compare that with the eigen-split $C=W\Lambda W^\top$ . Same shape: a turn, a diagonal, the turn back. So they must be the same thing:

W=V,\qquad \lambda_d=\frac{\sigma_d^2}{N}.

Why squared? $C$ is built from $X^\top X$ : the data appears twice, so a stretch of $\sigma$ becomes $\sigma^2$ .
Why divide by $N$ ? $X^\top X$ is a sum over all $N$ points, and a variance is an average.
$U$ or $V$ ? Ask which one has $D$ rows — that one lives in feature space and holds the directions. With points in rows (our way) it is $V$ . The slides store points in columns, so for them it is $U$ .

Most software takes this route. It never builds $C$ at all, which keeps more decimal places, and it can stop after the top few pieces.

The best squeeze: Eckart–Young

The SVD writes $X$ as a sum of simple layers, each one a single stretch $\sigma_d\,\mathbf u_d\mathbf v_d^\top$ . Keep only the top $M$ layers:

\begin{aligned}\tilde X_M&=\sigma_1\mathbf u_1\mathbf v_1^\top+\dots+\sigma_M\mathbf u_M\mathbf v_M^\top\\ &=U_M\Sigma_MV_M^\top.\end{aligned}

The Eckart–Young theorem says no matrix of rank $M$ comes closer to $X$ . And the error is made of exactly what you dropped:

\begin{gathered}\|X-\tilde X_M\|_2=\sigma_{M+1},\\ \|X-\tilde X_M\|_F=\sqrt{\sigma_{M+1}^2+\sigma_{M+2}^2+\cdots}\end{gathered}

(The first is the biggest stretch left over; the second is the square root of the sum of every squared entry of the error.)

Packing for the trip home

You are going home for Diwali and the suitcase fits $M$ things. The obvious plan: pack the biggest, most useful things first, and stop when it is full.

What is not obvious — and what Eckart–Young actually proves — is that no clever repacking beats this greedy order. Taking the top $M$ singular layers is not just sensible. It is the best there is.

Try: drag $k$ from 1 upward. By $k=6$ you can see the sun, the hills and the tree; by $k=20$ it is hard to tell from the original. The error readout always equals the first dropped singular value (spectral) and the root of the sum of the dropped squares (Frobenius). Then open the data cloud tab.

layers kept k6

the original

rebuilt from 6 layers

drag the picture to orbit

The realization

$\begin{gathered}C=V\,\frac{\Sigma^2}{N}\,V^\top\\ W=V,\qquad \lambda_d=\frac{\sigma_d^2}{N}\end{gathered}$

The principal directions are the right singular vectors of the centred data. Cutting the SVD after $M$ layers is the best possible rank- $M$ copy of the data — PCA again, seen as compression.

Pause & predict

A centred data matrix has $N=100$ rows and singular values $20,\ 10,\ 5,\ 1$ . What are the eigenvalues of $C$ ?

Pause & predict

Same matrix. You keep the best rank-2 copy. How big is the error in the two norms?

If you want the algebra · 2 proofs, step by step

Prove it · the SVD hands you the components

Claim. If the centred $X=U\Sigma V^\top$ ( $U^\top U=I$ , $V^\top V=I$ , $\Sigma$ diagonal), then $C=V\big(\Sigma^2/N\big)V^\top$ : the columns of $V$ are the principal directions and $\lambda_d=\sigma_d^2/N$ . The scores are $Z=XV=U\Sigma$ .

1

Substitute and simplify:

\begin{aligned}C&=\frac1N(U\Sigma V^\top)^\top(U\Sigma V^\top)\\ &=\frac1N V\Sigma^\top(U^\top U)\Sigma V^\top\\ &=V\,\frac{\Sigma^2}{N}\,V^\top.\end{aligned}

U^\top U=I

because

U

's columns are orthonormal;

\Sigma^\top=\Sigma

because it is diagonal.

2

Multiply on the right by

V

:

CV=V(\Sigma^2/N)

. Column

d

of this says

C\mathbf v_d=(\sigma_d^2/N)\mathbf v_d

. So

\mathbf v_d

is a unit eigenvector with eigenvalue

\sigma_d^2/N

. And

XV=U\Sigma V^\top V=U\Sigma

. ∎ In the slides' layout (points as columns),

S=\tfrac1N XX^\top=U(\Sigma\Sigma^\top/N)U^\top

, so there the directions are the columns of

U

. Pick the factor with

D

rows.

Prove it · the error of the truncated SVD

Claim. With $\tilde X_M=\sum_{d\le M}\sigma_d\mathbf u_d\mathbf v_d^\top$ : $\|X-\tilde X_M\|_2=\sigma_{M+1}$ and $\|X-\tilde X_M\|_F^2=\sum_{d>M}\sigma_d^2$ . (Eckart–Young adds that no rank- $M$ matrix does better; that part is stated, not proved here.)

1

The SVD is a sum of layers,

X=\sum_d\sigma_d\mathbf u_d\mathbf v_d^\top

. So the leftover is itself an SVD, made only of the dropped layers:

X-\tilde X_M=\sum_{d>M}\sigma_d\,\mathbf u_d\mathbf v_d^\top.

Its singular values are exactly

\sigma_{M+1},\sigma_{M+2},\dots

.

2

The spectral norm of any matrix is its largest singular value, so

\|X-\tilde X_M\|_2=\sigma_{M+1}

. The squared Frobenius norm is the sum of its squared singular values (it is

\operatorname{tr}(E^\top E)

, and the trace is the sum of the eigenvalues

\sigma_d^2

), so

\|X-\tilde X_M\|_F=\sqrt{\sigma_{M+1}^2+\sigma_{M+2}^2+\cdots}

. ∎ Singular values

20,10,5,1

,

M=2

: errors

5

and

\sqrt{26}\approx5.10

. And

\|X-\tilde X_M\|_F^2/N=\sum_{d>M}\sigma_d^2/N=\sum_{d>M}\lambda_d

— the rebuild error of §9 again.

In one sentence: substituting $X=U\Sigma V^\top$ into $C$ gives $W=V$ and $\lambda=\sigma^2/N$ , and cutting the SVD after $M$ layers is the best rank- $M$ copy of the data, with an error made of the dropped singular values.

12

Finding the top direction by just multiplying

Imagine this

At the school function, the microphone gets too close to the speaker. Any small sound goes round the loop — mic, amplifier, speaker, mic — and every trip makes one pitch a little louder than all the others.

A few seconds later that one pitch is all you can hear: the howl. Power iteration is that loop, used on purpose.

By hand, you find eigenvalues by solving $\det(C-\lambda I)=0$ . For a $2\times2$ matrix that is a quadratic. For $3\times3$ it is a cubic, and $4\times4$ a quartic — there are formulas, though nobody enjoys them.

At $5\times5$ the method dies, and not because nobody has been clever enough. The Abel–Ruffini theorem proves that a general polynomial of degree 5 or more has no formula for its roots using $+,-,\times,\div$ and roots. Not "none is known" — none can exist. So every real eigenvalue program iterates: start with a guess, improve it, stop when it stops changing.

There is a second reason to iterate. A full eigen-split of a $D\times D$ matrix costs about $D^3$ steps and returns all $D$ directions. PCA usually wants two, or ten. Paying for hundreds and binning most of them is waste.

The simplest iteration goes straight for the top direction. Start with any arrow $\mathbf x_0$ and repeat:

\mathbf x_{k+1}=\frac{C\,\mathbf x_k}{\|C\,\mathbf x_k\|}.

Multiply by $C$ , shrink back to length 1, repeat. That is the whole method.

Try it on $C=\begin{bmatrix}5&4\\4&5\end{bmatrix}$ from $\mathbf x_0=(1,0)$ . First pass: $C\mathbf x_0=(5,4)$ , whose length is $\sqrt{41}$ , so $\mathbf x_1\approx(0.781,\ 0.625)$ . Second pass: $C(5,4)=(41,40)$ , so $\mathbf x_2\approx(0.716,\ 0.698)$ . It is closing in on the answer $\tfrac1{\sqrt2}(1,1)\approx(0.707,\ 0.707)$ fast.

Why it works. Write the start in terms of the eigenvectors: $\mathbf x_0=c_1\mathbf w_1+c_2\mathbf w_2$ . Each multiplication by $C$ stretches the $\mathbf w_1$ part by $\lambda_1$ and the $\mathbf w_2$ part by $\lambda_2$ . After $k$ passes:

\begin{aligned}C^k\mathbf x_0&=c_1\lambda_1^{\,k}\mathbf w_1+c_2\lambda_2^{\,k}\mathbf w_2\\ &=\lambda_1^{\,k}\Big(c_1\mathbf w_1+c_2\Big(\frac{\lambda_2}{\lambda_1}\Big)^{k}\mathbf w_2\Big).\end{aligned}

The ratio $\lambda_2/\lambda_1$ is less than 1, so the wrong part fades away pass after pass. Here $\lambda_2/\lambda_1=1/9$ : each pass shrinks the wrong part nine times.

When it crawls

If the top two eigenvalues are close — say $5.0$ and $4.9$ — the ratio is $0.98$ , and each pass shrinks the wrong part by only 2 %. Progress is very slow. But then the top two directions carry almost the same spread anyway, so "which one comes first" hardly matters. Real libraries use smarter versions of this loop for that case.

Try: at $\lambda_2/\lambda_1=1/9$ press ▶: the arrow lands in two or three passes. Drag the ratio to $0.98$ and press ▶ again — it crawls, and the line on the right barely slopes. The 3-D tab runs the same loop on a $3\times3$ matrix, hopping across a sphere.

λ₂ / λ₁0.111

start at0°

drag the picture to orbit

Here $C$ has eigenvalues $6,\ 3,\ 1$ , so each pass shrinks the part along $\mathbf w_2$ to half and the part along $\mathbf w_3$ to a sixth.

The realization

$\mathbf x_{k+1}=\frac{C\mathbf x_k}{\|C\mathbf x_k\|}$

No formula can find the eigenvalues of a big matrix, so software multiplies instead. Each multiplication by $C$ favours the direction $C$ stretches most: the wrong part shrinks by $\lambda_2/\lambda_1$ every pass, until only the top direction is left.

Pause & predict

Power iteration on $C=\begin{bmatrix}5&4\\4&5\end{bmatrix}$ from $\mathbf x_0=(1,0)$ . After one pass, where is the arrow, and by how much has the wrong part shrunk?

If you want the algebra · 1 proof, step by step

Prove it · power iteration closes in by λ₂/λ₁

Claim. If $\lambda_1>|\lambda_2|\ge\dots$ and $\mathbf x_0$ has a non-zero part $c_1$ along $\mathbf w_1$ , the direction of $C^k\mathbf x_0$ tends to $\pm\mathbf w_1$ , and in two dimensions the tangent of the angle to $\mathbf w_1$ is multiplied by exactly $\lambda_2/\lambda_1$ each pass.

1

The rescaling in

\mathbf x_{k+1}=C\mathbf x_k/\|C\mathbf x_k\|

only changes the length, never the direction, so

\mathbf x_k

points the same way as

C^k\mathbf x_0

. The division by the length only stops the numbers overflowing.

2

Expand

\mathbf x_0=\sum_d c_d\mathbf w_d

. Each multiplication scales the

d

-th part by

\lambda_d

:

\begin{aligned}C^k\mathbf x_0&=\sum_d c_d\lambda_d^{\,k}\mathbf w_d\\ &=\lambda_1^{\,k}\Big(c_1\mathbf w_1+\sum_{d\ge2}c_d\,r_d^{\,k}\,\mathbf w_d\Big),\end{aligned}

where

r_d=\lambda_d/\lambda_1

. Every ratio

\lambda_d/\lambda_1

is less than 1 in size, so every term but the first fades geometrically.

3

In two dimensions the angle

\theta_k

to

\mathbf w_1

has

\tan\theta_k=\dfrac{|c_2|\lambda_2^{\,k}}{|c_1|\lambda_1^{\,k}}=\tan\theta_0\Big(\dfrac{\lambda_2}{\lambda_1}\Big)^{k}

. ∎ For

C=\begin{bmatrix}5&4\\4&5\end{bmatrix}

from

(1,0)

:

\theta_0=45^\circ

, then

\tan\theta_1=1/9

(

6.34^\circ

),

\tan\theta_2=1/81

(

0.71^\circ

). On a log scale, a straight line with slope

\log(\lambda_2/\lambda_1)

.

In one sentence: no formula finds the eigenvalues of a big matrix, so software multiplies by $C$ and rescales, and each pass shrinks everything except the top direction by the factor $\lambda_2/\lambda_1$ .

13

When columns outnumber rows — the Gram trick

Imagine this

A hospital lab has tissue from 40 patients. For each one, a machine reads 12,000 genes. The spreadsheet is 40 rows tall and 12,000 columns wide — a class register with 40 students and twelve thousand subjects.

Most data is long: many rows, few columns. This data is wide. And the usual recipe falls over on it.

The covariance matrix is always (number of columns) × (number of columns), no matter how few rows you have. Here that is $12{,}000\times12{,}000=1.44\times10^8$ numbers. At 8 bytes each, that is about 1.152 GB — for a dataset that is only a few megabytes. Worse, an eigen-split costs about $D^3\approx1.7\times10^{12}$ steps. Hours of work, to learn from 40 patients.

The tempting wrong fix

" $X^\top X$ is huge, so use $XX^\top$ instead — it is only $40\times40$ !" Right instinct, wrong statement. $XX^\top$ is not the covariance matrix. Its rows and columns are indexed by patients, not genes, and its eigenvectors have 40 entries, when we need 12,000. We can still use it — as a stepping stone.

The trick is one multiplication. Start from the eigen-equation we want, $\tfrac1N X^\top X\,\mathbf w=\lambda\mathbf w$ , and multiply both sides on the left by $X$ :

\frac1N X X^\top\,(X\mathbf w)=\lambda\,(X\mathbf w).

Give the two pieces names. $K=\tfrac1N XX^\top$ is the small $N\times N$ table, called the Gram matrix. And $\mathbf u=X\mathbf w$ has $N$ entries. Then

K\mathbf u=\lambda\,\mathbf u.

An eigen-problem on a $40\times40$ table. And the $\lambda$ is the same $\lambda$ .

Getting back. Solving the small problem gives $\mathbf u$ . To get $\mathbf w$ , multiply by $X^\top$ : then $C(X^\top\mathbf u)=\lambda(X^\top\mathbf u)$ , so $X^\top\mathbf u$ is an eigenvector of $C$ with that same $\lambda$ . It points the right way but has the wrong length, so finish with

\mathbf w=\frac{X^\top\mathbf u}{\|X^\top\mathbf u\|}.

Forgetting this last step is the most common slip, and it quietly breaks "spread $=\lambda$ ".

Nothing is lost

$C$ has 12,000 eigenvalues. But 40 points can only span a flat piece of space of at most 40 dimensions — and centring (making the rows add to zero) takes away one more. So at most $N-1=39$ eigenvalues can be non-zero. The other 11,961 are exactly zero and carry no spread at all.

The small table $K$ already holds every non-zero eigenvalue there was. The Gram trick is not an approximation. It is the whole answer, bought cheaply.

Try: press gene study: $C$ needs over a gigabyte, $K$ a few kilobytes. Push $D$ to $100{,}000$ and $C$ will not fit in the laptop at all. Then press new random data below: the non-zero eigenvalues of the $5\times5$ and $3\times3$ matrices always agree, and the recovered direction always matches.

rows N40

columns D12,000

A wide dataset you can hold in your hand N = 3 points, D = 5 columns, centred

The realization

$\begin{gathered}K=\frac1N XX^\top,\qquad K\mathbf u=\lambda\mathbf u\\ \mathbf w=\frac{X^\top\mathbf u}{\|X^\top\mathbf u\|}\end{gathered}$

When columns outnumber rows, solve the small $N\times N$ problem instead. The non-zero eigenvalues are identical, and one multiplication by $X^\top$ — then a rescale — turns each small eigenvector into a principal direction.

Pause & predict

12,000 genes, 40 patients, centred. How much memory does $C$ need in 8-byte numbers, and how many of its eigenvalues can be non-zero?

If you want the algebra · 1 proof, step by step

Prove it · the Gram trick, both ways

Claim. With $C=\tfrac1N X^\top X$ ( $D\times D$ ) and $K=\tfrac1N XX^\top$ ( $N\times N$ ): (a) if $C\mathbf w=\lambda\mathbf w$ with $\lambda\ne0$ , then $\mathbf u=X\mathbf w$ satisfies $K\mathbf u=\lambda\mathbf u$ and $\mathbf u\ne\mathbf 0$ ; (b) if $K\mathbf u=\lambda\mathbf u$ with $\lambda\ne0$ , then $C(X^\top\mathbf u)=\lambda(X^\top\mathbf u)$ , and for a unit $\mathbf u$ , $\|X^\top\mathbf u\|=\sqrt{N\lambda}$ .

1

(a) Multiply

\tfrac1N X^\top X\mathbf w=\lambda\mathbf w

on the left by

X

and regroup:

\begin{aligned}\frac1N XX^\top(X\mathbf w)&=\lambda\,(X\mathbf w),\\ \text{that is}\quad K\mathbf u&=\lambda\mathbf u.\end{aligned}

\mathbf u

is not zero:

\|X\mathbf w\|^2=N\,\mathbf w^\top C\mathbf w=N\lambda>0

. So every non-zero eigenvalue of

C

is also an eigenvalue of

K

.

2

(b) Multiply

\tfrac1N XX^\top\mathbf u=\lambda\mathbf u

on the left by

X^\top

:

\begin{aligned}\frac1N X^\top X\,(X^\top\mathbf u)&=\lambda\,(X^\top\mathbf u),\\ \text{that is}\quad C\,(X^\top\mathbf u)&=\lambda\,(X^\top\mathbf u).\end{aligned}

And every non-zero eigenvalue of

K

is one of

C

. The two lists of non-zero eigenvalues are identical.

3

Its length:

\|X^\top\mathbf u\|^2=\mathbf u^\top XX^\top\mathbf u=N\,\mathbf u^\top K\mathbf u=N\lambda\,\mathbf u^\top\mathbf u=N\lambda

. So

\mathbf w=X^\top\mathbf u/\sqrt{N\lambda}

is the unit direction. ∎ Not normalising leaves a vector of length

\sqrt{N\lambda}

, and its "spread" comes out

N\lambda

times too big. Rank:

X

has

N

rows adding to

\mathbf 0

, so

\operatorname{rank}X\le N-1

and at most

N-1

eigenvalues are non-zero.

In one sentence: when $D\gg N$ , eigen-split the small $N\times N$ Gram matrix instead — same non-zero eigenvalues — and turn each $\mathbf u$ into a direction with $\mathbf w=X^\top\mathbf u/\|X^\top\mathbf u\|$ .

14

The recipe, and the traps

Imagine this

Dosa batter has a recipe: soak, grind, ferment, cook. Skip a step and you still get something on the tawa — just not a dosa.

PCA has a recipe too. Each step is there for a reason, and each skipped step has a way of going quietly wrong.

Everything so far fits in four steps, plus an optional fifth:

Centre. Subtract each column's mean $\mu_d$ . Now every column averages to zero.
Standardise. Divide each column by its standard deviation $\sigma_d$ (the square root of its spread). Now every column has spread 1 and no units.
Eigen-split. Build $C=\tfrac1N X^\top X$ , find its eigenvalues and eigenvectors, make each eigenvector length 1, and sort biggest first. Keep the top $M$ as the columns of $W$ .
Project. $Z=XW$ . You started with $D$ columns and now have $M$ . That one multiplication is the dimension reduction.
(optional) Undo. To see a rebuilt point in the original units, undo steps 2 and 1 in reverse order: $x=\tilde x\,\sigma_d+\mu_d$ .

A new point (a fresh customer, a test row) goes through the same steps with the training $\mu$ , $\sigma$ and $W$ . Never its own — one point has no spread — and never the test set's, which quietly leaks the test data into the model.

Try it. Training means $\mu=(4,10)$ , standard deviations $\sigma=(2,5)$ , kept direction $\mathbf w_1=(0.6,\ 0.8)$ , dropped direction $\mathbf w_2=(-0.8,\ 0.6)$ . A new point $(6,20)$ arrives.

Standardise: $\big(\tfrac{6-4}{2},\ \tfrac{20-10}{5}\big)=(1,2)$ .
Score: $z=0.6(1)+0.8(2)=2.2$ . Rebuild: $2.2\,(0.6,\ 0.8)=(1.32,\ 1.76)$ .
Error: $(1-1.32)^2+(2-1.76)^2=0.1024+0.0576=0.16$ . And along the dropped direction, $z_2=-0.8+1.2=0.4$ , so $z_2^2=0.16$ . The same, as §9 promised.

The traps

1 · Units decide the answer. PCA chases spread, and spread depends on units. Measure height in metres and weight in kilograms: weight's numbers are simply bigger, so its spread is about 8,600 times larger. The raw PC1 then puts a loading of $1.00$ on weight and $0.01$ on height — it is just the weight column. After standardising, both columns compete fairly and the loadings come out $0.71$ and $0.71$ . (If all columns share one unit and their spreads are real information, centre only. Decide on purpose.)

2 · PCA is blind to $y$ . It ranks directions by spread in $\mathbf x$ , and it has no idea whether that spread has anything to do with what you want to predict. It can rank them exactly backwards. In photos, the biggest spread is often the lighting, not the face. In gene data it is often which machine or batch ran the test. If you need the target kept, use a method that looks at $y$ (such as partial least squares or linear discriminant analysis) instead of, or alongside, PCA.

3 · Outliers pull the components. Spread adds up squared distances, so one far-away point counts enormously. One mistyped value can swing PC1 toward itself. Look at the data first.

4 · Signs are arbitrary. $-\mathbf w$ is as good as $\mathbf w$ . Read patterns, not signs.

5 · Straight lines only. Every component is a straight mix of the columns. Data on a curve or a spiral needs several components to describe one curved direction. (Curved cousins exist — kernel PCA, t-SNE, UMAP — but that is another story.)

Try: step through (a) to (f). Then on the unit trap, switch standardising off and on: PC1 swings from "all weight" to an equal mix. On blind to y, compare the two small plots — the component PCA would keep says nothing about $y$ .

The realization

$\begin{gathered}\text{centre}\ \to\ \text{standardise}\\ \to\ \text{eigen-split}\ \to\ \text{project}\end{gathered}$

Fit $\mu$ , $\sigma$ and $W$ once, on training data, and reuse them for everything new. And remember what PCA cannot see: units nobody told it about, the target $y$ , and curves.

Pause & predict

A second new point $(8,5)$ arrives for the same fitted PCA ( $\mu=(4,10)$ , $\sigma=(2,5)$ , $\mathbf w_1=(0.6,\ 0.8)$ ). What is its score $z$ ?

In one sentence: centre, standardise, eigen-split and project with numbers fitted once on training data — and never forget that PCA is blind to units you did not fix, to the target, and to curves.

15

One example, start to finish

Imagine this

You have seen every part of the engine on its own. Now take the car out for a full drive — from the five raw points to their one-number summary, with every check along the way.

The data: $(1,2),\ (4,5),\ (7,8),\ (8,4),\ (10,6)$ . Reduce it from two numbers per point to one.

Step 1 · Centre. The mean is $(6,5)$ . Subtract it:

X=\begin{bmatrix}-5&-3\\ -2&0\\ 1&3\\ 2&-1\\ 4&1\end{bmatrix}\qquad\text{(each column adds to }0\text{ }\checkmark\text{)}

We skip standardising: both columns are in the same units with similar spreads.

Step 2 · Build $C$ (divide by $N=5$ ):

C=\frac15\begin{bmatrix}50&20\\20&20\end{bmatrix}=\begin{bmatrix}10&4\\4&4\end{bmatrix},\qquad\operatorname{tr}(C)=14.

Step 3 · Eigenvalues.

\begin{aligned}\det(C-\lambda I)&=(10-\lambda)(4-\lambda)-16\\ &=\lambda^2-14\lambda+24=0,\end{aligned}

\lambda=\frac{14\pm\sqrt{196-96}}{2}=\frac{14\pm10}{2}\ \Longrightarrow\ \lambda_1=12,\ \ \lambda_2=2.

Two instant checks: $12+2=14=\operatorname{tr}(C)$ ✓ and $12\times2=24=\det C$ ✓. Shares: $12/14=85.71\%$ and $2/14=14.29\%$ .

Step 4 · Eigenvectors, then length 1. For $\lambda_1=12$ : $-2a+4b=0$ , so $a=2b$ : the direction $(2,1)$ , length $\sqrt5$ . For $\lambda_2=2$ : $8a+4b=0$ , so $b=-2a$ : the direction $(1,-2)$ .

\mathbf w_1=\frac1{\sqrt5}\begin{bmatrix}2\\1\end{bmatrix}\approx\begin{bmatrix}0.894\\0.447\end{bmatrix},\qquad \mathbf w_2=\frac1{\sqrt5}\begin{bmatrix}1\\-2\end{bmatrix}.

Check: $\mathbf w_1^\top\mathbf w_2=\tfrac15(2-2)=0$ ✓, and both have length 1 ✓.

Step 5 · Project. One dot product per row, $z_i=\mathbf w_1^\top\mathbf x_i$ :

\mathbf z=\frac1{\sqrt5}\big(-13,\ -4,\ 5,\ 3,\ 9\big)\approx\big(-5.814,\ -1.789,\ 2.236,\ 1.342,\ 4.025\big).

Five points, five numbers. The reduction is done.

Step 6 · Three checks.

The scores average to zero: $-13-4+5+3+9=0$ ✓.
Their spread is $\lambda_1$ : $\tfrac15\cdot\tfrac{169+16+25+9+81}{5}=\tfrac{300}{25}=12$ ✓.
The dropped direction holds the rest: scores $\tfrac1{\sqrt5}(1,-2,-5,4,2)$ , spread $\tfrac{50}{25}=2=\lambda_2$ , and $12+2=14$ ✓. Nothing went missing.

Now run it yourself — on these points, on the four points of Practice Problem 1, on the nine-point example from the slides, or on any points you drag around.

Try: start with the five points and check every card against the page above. Then load the slides' nine points: $\lambda_1\approx10.103$ and $\mathbf w_1\approx(0.088,\ 0.996)$ . Then drag one point far away and watch one outlier drag PC1 toward itself.

your points

drag the points

The realization

Mean → centre → $C=\tfrac1N X^\top X$ → $\det(C-\lambda I)=0$ → eigenvectors of length 1 → scores. And three free checks at the end: $\sum\lambda=\operatorname{tr}C$ , $\prod\lambda=\det C$ , and "spread of the scores $=\lambda_1$ ".

Pause & predict

A classmate gets eigenvalues $13$ and $1$ for $C=\begin{bmatrix}10&4\\4&4\end{bmatrix}$ . Which quick check catches the mistake?

In one sentence: centre, build $C$ , solve the quadratic, make the eigenvectors length 1, project — and let the trace, the determinant and the spread of the scores check your work for free.

16

What to carry forward

One question ran through this whole unit: from which direction does the data look most spread out? It turned into a matrix, then a leash, then an eigenvector — and then it showed up three more times, wearing different clothes. Here is the whole unit on one card.

Part	What to remember
The problem	$\max_{\mathbf w}\ \mathbf w^\top C\mathbf w$ subject to $\mathbf w^\top\mathbf w=1$ — only the direction matters, never the length
The derivation, in six lines	① $\mathbf z=X\mathbf w$ ② $\tfrac1N\mathbf z^\top\mathbf z=\mathbf w^\top C\mathbf w$ ③ $L=\mathbf w^\top C\mathbf w-\lambda(\mathbf w^\top\mathbf w-1)$ ④ $2C\mathbf w-2\lambda\mathbf w=\mathbf 0$ ⑤ $C\mathbf w=\lambda\mathbf w$ ⑥ $\mathbf w^\top C\mathbf w=\lambda$
The five facts	directions are eigenvectors, $C\mathbf w_d=\lambda_d\mathbf w_d$ · spread along each is $\lambda_d$ · $\operatorname{tr}C=\sum\lambda_d$ · $\operatorname{Cov}(Z)=W^\top CW=\Lambda$ · $\lambda_d=\sigma_d^2/N$
The recipe	centre · standardise · $C=\tfrac1N X^\top X$ , eigen-split, length 1, sort · keep $M$ for your target share · $Z=XW$ ; new points use the training $\mu,\sigma,W$
The six traps	dividing by $N-1$ · not making eigenvectors length 1 · not centring · standardising new data with its own $\mu,\sigma$ · expecting $WW^\top=I$ (only $W^\top W=I$ ) · assuming the top component predicts $y$
When things get big	$D\ge5$ : no formula exists, so iterate · only the top one: $\mathbf x_{k+1}=C\mathbf x_k/\\|C\mathbf x_k\\|$ · $D\gg N$ : use $K=\tfrac1N XX^\top$ , then $\mathbf w=X^\top\mathbf u/\\|X^\top\mathbf u\\|$ · best rank- $M$ copy: $U_M\Sigma_MV_M^\top$
Three views, one answer	most spread kept · least rebuild error · best truncated SVD — all the top eigenvectors of $C$

The one thing to remember

Ask a geometric wish, put it on a leash, and the answer is an eigenvector.

"Most spread" became $\mathbf w^\top C\mathbf w$ . The leash $\mathbf w^\top\mathbf w=1$ became a fine. The fine became the eigenvalue, and the eigenvalue became the spread. Everything else — the budget, the rebuild error, the uncorrelated scores, the SVD, the Gram trick — is that one idea seen from another side.

Where this goes next. Unit 13 is about support vector machines. It makes the same move you just made: it takes a geometric wish — the widest possible street between two groups of points — and turns it into a constrained optimisation with fines. You already met a two-point version at the end of Unit 11. And when Unit 13 solves the problem from the fines' side, the data shows up only through dot products between points: a Gram matrix, just like the $K$ of §13.

In one sentence: PCA turns "which way does the data spread most?" into "which eigenvector of $C$ has the biggest eigenvalue?", and every other view of it — budget, rebuild error, uncorrelated scores, SVD — lands on the same answer.

17

Practice arena — twelve problems, solved in full

Twelve problems, each a different shape: raw data all the way to scores, a derivation with three faults to find, a new point pushed through a fitted model, a $3\times3$ matrix read by its pattern of zeros, data far wider than it is tall, a spread budget, singular values turned into components — then the nine-point example from the slides, two passes of power iteration, a question asked backwards, a loadings audit, and the Gram trick on real numbers. Every number is machine-verified.

Many books write $\Sigma$ for the covariance matrix and $\alpha$ for a direction, and call the first score $Y_1=\alpha^\top X$ . They are exactly our $C$ , $\mathbf w$ and $z_1$ . Three habits do most of the work. Check as you go: centred columns add to zero, $\sum\lambda=\operatorname{tr}C$ , $\prod\lambda=\det C$ . Always make eigenvectors length 1 before you use them. And divide by $N$ .

Problem 1easy

Four observations on two variables: $(2,3),\ (4,7),\ (6,5),\ (8,9)$ . (a) Find the mean, write the centred data matrix, and build the covariance matrix (divide by $N$ ). (b) Find its eigenvalues and unit eigenvectors. (c) Find the first principal component score of each observation, check that their spread equals $\lambda_1$ , and give the share of the total spread that the first component keeps.

What this tests. The full computation from raw numbers to scores. How to attack it. Always the same five moves: mean → centre → $\tfrac1N X^\top X$ → characteristic polynomial → length 1. Check the centred columns add to zero before going on; check the eigenvalues with the trace and the determinant.

Show the full solution

(a) Mean and centring.

\mu_1=\tfrac{2+4+6+8}{4}=5

,

\mu_2=\tfrac{3+7+5+9}{4}=6

. Subtract

(5,6)

from every row:

X=\begin{bmatrix}-3&-3\\-1&1\\1&-1\\3&3\end{bmatrix}\qquad\text{columns add to }0\ \checkmark

(a) Covariance.

\sum x_1^2=9+1+1+9=20

,

\sum x_2^2=20

,

\sum x_1x_2=9-1-1+9=16

. Divide by

N=4

:

C=\frac14\begin{bmatrix}20&16\\16&20\end{bmatrix}=\begin{bmatrix}5&4\\4&5\end{bmatrix}.

(b) Eigenvalues.

\det(C-\lambda I)=(5-\lambda)^2-16=0\ \Rightarrow\ 5-\lambda=\pm4\ \Rightarrow\ \lambda_1=9,\ \lambda_2=1.

Checks:

9+1=10=\operatorname{tr}C

✓ and

9\times1=9=25-16=\det C

✓.

(b) Eigenvectors. For

\lambda_1=9

:

-4a+4b=0

, so

a=b

, the direction

(1,1)

of length

\sqrt2

. For

\lambda_2=1

:

4a+4b=0

, so

b=-a

.

\mathbf w_1=\frac1{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix},\qquad \mathbf w_2=\frac1{\sqrt2}\begin{bmatrix}1\\-1\end{bmatrix},\qquad \mathbf w_1^\top\mathbf w_2=\tfrac12(1-1)=0\ \checkmark

(c) Scores.

z=\tfrac1{\sqrt2}(x_1+x_2)

on each centred row:

\frac{-6}{\sqrt2}=-3\sqrt2\approx-4.243,\qquad \frac{0}{\sqrt2}=0,\qquad 0,\qquad \frac{6}{\sqrt2}=3\sqrt2\approx4.243.

They add to zero, so their spread is the mean of their squares:

\tfrac{18+0+0+18}{4}=9=\lambda_1

✓. Share:

\tfrac{9}{9+1}=90\%

.

answers at a glance: $\boldsymbol\mu=(5,6)$ ; $C=\begin{bmatrix}5&4\\4&5\end{bmatrix}$ ; $\lambda=9,\ 1$ ; $\mathbf w_1=\tfrac1{\sqrt2}(1,1)$ , $\mathbf w_2=\tfrac1{\sqrt2}(1,-1)$ ; scores $-4.243,\ 0,\ 0,\ 4.243$ ; spread $9$ ; share $90\%$ .

Problem 2medium

A student finds the first principal component of $C=\begin{bmatrix}5&2\\2&8\end{bmatrix}$ with a Lagrange multiplier. Their complete attempt:

Maximise $\mathbf w^\top C\mathbf w$ subject to $\mathbf w^\top\mathbf w=1$ .
$L(\mathbf w,\lambda)=\mathbf w^\top C\mathbf w-\lambda(\mathbf w^\top\mathbf w-1)$ .
$\partial L/\partial\mathbf w=2C\mathbf w-\lambda\mathbf w=\mathbf 0$ , so $C\mathbf w=\tfrac12\lambda\mathbf w$ .
$\det(C-\lambda I)=\lambda^2-13\lambda+36=0$ , so $\lambda=9$ and $\lambda=4$ .
For the larger root, $(C-9I)\mathbf w=\mathbf 0$ gives $\mathbf w=(1,2)$ , so $z_1=x_1+2x_2$ .
The spread of $z_1$ is $9$ , because the maximum spread is the largest eigenvalue.

Exactly three lines are faulty. (a) Name them and say in one sentence each what is wrong. (b) Redo the derivation correctly from the first faulty line, and give the correct $z_1$ and its spread. (c) Compute the spread of the student's $x_1+2x_2$ directly from $C$ , and state the general rule for an eigenvector that was not made length 1.

What this tests. Knowing the six-line derivation well enough to mark someone else's. How to attack it. At each line ask three questions: is the rule written as "something $=0$ "? is every derivative right? does the final vector have length 1? A line that survives all three is almost certainly fine.

Show the full solution

(a) The three faults. Lines 1, 2 and 4 are correct.

Line 3: the derivative of $\mathbf w^\top\mathbf w$ is $2\mathbf w$ , not $\mathbf w$ . The second term must be $-2\lambda\mathbf w$ . As written, the multiplier would be twice the eigenvalue.
Line 5: $(1,2)$ is the right direction but has length $\sqrt5$ ; the derivation assumed length 1.
Line 6: with the $\mathbf w$ of line 5, the spread is not $9$ . "Spread $=\lambda$ " holds only for a unit vector.

(b) Corrected. Both terms of

L

are quadratic forms:

\frac{\partial L}{\partial\mathbf w}=2C\mathbf w-2\lambda\mathbf w=\mathbf 0\ \Rightarrow\ C\mathbf w=\lambda\mathbf w.

Line 4 stands:

(5-\lambda)(8-\lambda)-4=\lambda^2-13\lambda+36=0

, so

\lambda=\tfrac{13\pm5}{2}

:

\lambda_1=9

,

\lambda_2=4

. Checks:

9+4=13=\operatorname{tr}C

✓,

9\times4=36=40-4=\det C

✓.

(b) The direction. For

\lambda_1=9

:

-4w_1+2w_2=0

, so

w_2=2w_1

: direction

(1,2)

, length

\sqrt5

.

\mathbf w_1=\frac1{\sqrt5}\begin{bmatrix}1\\2\end{bmatrix},\qquad z_1=\frac{x_1+2x_2}{\sqrt5},\qquad \text{spread}=\lambda_1=9.

For completeness,

\lambda_2=4

gives

\mathbf w_2=\tfrac1{\sqrt5}(-2,1)

, and

\mathbf w_1^\top\mathbf w_2=\tfrac15(-2+2)=0

✓. The first component keeps

9/13\approx69.2\%

.

(c) The student's spread.

\operatorname{Var}(x_1+2x_2)=\operatorname{Var}(x_1)+4\operatorname{Var}(x_2)+4\operatorname{Cov}(x_1,x_2)=5+32+8=45.

Five times the claimed

9

. In general, if

C\mathbf w=\lambda\mathbf w

then

\mathbf w^\top C\mathbf w=\lambda\|\mathbf w\|^2

. Here

\|\mathbf w\|^2=5

, and

5\times9=45

.

answers at a glance: faulty lines 3, 5, 6; $C\mathbf w=\lambda\mathbf w$ ; $\lambda=9,\ 4$ ; $\mathbf w_1=\tfrac1{\sqrt5}(1,2)$ ; $z_1=(x_1+2x_2)/\sqrt5$ with spread $9$ ( $69.2\%$ ); $\operatorname{Var}(x_1+2x_2)=45=\lambda\|\mathbf w\|^2$ .

Problem 3easy

A PCA is fitted on a two-variable training set with means $\boldsymbol\mu=(4,10)$ and standard deviations $\boldsymbol\sigma=(2,5)$ . On the standardised data the kept direction is $\mathbf w_1=(3/5,\ 4/5)$ and the dropped one is $\mathbf w_2=(-4/5,\ 3/5)$ . A new observation $\mathbf x^\ast=(6,20)$ arrives. (a) Standardise it, saying which mean and standard deviation you use and why. (b) Find its score $z^\ast$ and its rebuild $\tilde{\mathbf x}^\ast=z^\ast\mathbf w_1$ (standardised scale). (c) Find the squared rebuild error and check that it equals $z_2^2$ . (d) Undo the standardising to give the rebuilt point in the original units, and its squared error there. Is it still $z_2^2$ ?

What this tests. Using a fitted PCA on new data, and where the error goes. How to attack it. The only idea is that $\boldsymbol\mu$ , $\boldsymbol\sigma$ and $W$ come from training. After that it is arithmetic. Get the error once by subtraction and confirm it with $z_2^2$ .

Show the full solution

(a) Standardise with the training numbers. One point has no mean or spread of its own, and using test statistics would leak the test data into the model:

\mathbf x^\ast_{\text{std}}=\Big(\frac{6-4}{2},\ \frac{20-10}{5}\Big)=(1,\ 2).

(b) Score and rebuild.

\begin{aligned}z^\ast&=\tfrac35(1)+\tfrac45(2)=\tfrac{11}{5}=2.2,\\ \tilde{\mathbf x}^\ast&=2.2\,(0.6,\ 0.8)=(1.32,\ 1.76).\end{aligned}

Close to

(1,2)

, but not equal: we kept one of two directions.

(c) The error.

\begin{aligned}\mathbf r&=(1-1.32,\ 2-1.76)=(-0.32,\ 0.24),\\ \|\mathbf r\|^2&=0.1024+0.0576=0.16.\end{aligned}

Along the dropped direction:

z_2=-\tfrac45(1)+\tfrac35(2)=\tfrac25=0.4

, and

z_2^2=0.16

✓. Pythagoras in the basis

\{\mathbf w_1,\mathbf w_2\}

, which is orthonormal:

-\tfrac{12}{25}+\tfrac{12}{25}=0

, and both lengths are

1

.

(d) Back to original units. Undo in reverse order — multiply by

\sigma

, then add

\mu

:

\tilde{\mathbf x}^\ast_{\text{orig}}=(1.32\times2+4,\ \ 1.76\times5+10)=(6.64,\ 18.8).

The error there is

(6-6.64)^2+(20-18.8)^2=0.4096+1.44=1.8496

. That is not

0.16

: undoing the standardising stretches the two axes by different amounts (

2

and

5

), so Pythagoras in the standardised basis no longer gives the raw error. The clean "error

=z_2^2

" lives on the scale where the PCA was fitted.

answers at a glance: (a) $(1,2)$ , using the training $\boldsymbol\mu,\boldsymbol\sigma$ ; (b) $z^\ast=2.2$ , $\tilde{\mathbf x}^\ast=(1.32,\ 1.76)$ ; (c) error $0.16=z_2^2$ with $z_2=0.4$ ; (d) $(6.64,\ 18.8)$ , squared error $1.8496$ — not $z_2^2$ .

Problem 4medium

Three variables have covariance matrix $C=\begin{bmatrix}4&2&0\\2&4&0\\0&0&3\end{bmatrix}$ . (a) Without expanding the full cubic, say what the zeros tell you about $x_3$ , and write down all three eigenvalues. Check them against $\operatorname{tr}C$ and $\det C$ . (b) Find the three unit eigenvectors and confirm they meet at right angles. (c) Write $z_1$ and its spread. Then show that keeping $z_1$ and $z_2$ rebuilds $x_3$ exactly but not $x_1,x_2$ ; name what is lost and check that its spread is $\lambda_3$ .

What this tests. Reading structure before grinding. How to attack it. A variable uncorrelated with all the others splits off: its variance is an eigenvalue, and its axis is an eigenvector. That turns a cubic into a quadratic plus a freebie.

Show the full solution

(a) The pattern of zeros.

\operatorname{Cov}(x_3,x_1)=\operatorname{Cov}(x_3,x_2)=0

:

x_3

moves independently of the other two. So

C

splits into blocks,

A=\begin{bmatrix}4&2\\2&4\end{bmatrix}

and

[3]

, and its eigenvalues are the blocks' eigenvalues pooled. The

1\times1

block gives

3

. For

A

:

(4-\lambda)^2-4=0\Rightarrow4-\lambda=\pm2\Rightarrow\lambda=6,\ 2

.

\lambda_1=6,\quad\lambda_2=3,\quad\lambda_3=2.

Checks:

6+3+2=11=4+4+3

✓;

6\times3\times2=36=3\times(16-4)=\det C

✓.

(b) Eigenvectors. For

6

:

-2a+2b=0\Rightarrow a=b

. For

3

: the

x_3

axis itself. For

2

:

2a+2b=0\Rightarrow b=-a

.

\mathbf w_1=\frac1{\sqrt2}\begin{bmatrix}1\\1\\0\end{bmatrix},\quad \mathbf w_2=\begin{bmatrix}0\\0\\1\end{bmatrix},\quad \mathbf w_3=\frac1{\sqrt2}\begin{bmatrix}1\\-1\\0\end{bmatrix}.

\mathbf w_1^\top\mathbf w_3=\tfrac12(1-1)=0

, and

\mathbf w_2

has zeros where the others do not, so all three pairs meet at right angles. Spot check:

C\mathbf w_1=\tfrac1{\sqrt2}(6,6,0)=6\mathbf w_1

✓.

(c) Keep two.

z_1=\tfrac{x_1+x_2}{\sqrt2}

with spread

\lambda_1=6

. With

W=[\mathbf w_1\ \mathbf w_2]

, the flattener is

WW^\top=\mathbf w_1\mathbf w_1^\top+\mathbf w_2\mathbf w_2^\top=\begin{bmatrix}\tfrac12&\tfrac12&0\\ \tfrac12&\tfrac12&0\\0&0&1\end{bmatrix},\qquad \tilde{\mathbf x}=\Big(\frac{x_1+x_2}2,\ \frac{x_1+x_2}2,\ x_3\Big).

So

x_3

comes back exactly, while

x_1

and

x_2

are both replaced by their average.

(c) What is lost.

\mathbf x-\tilde{\mathbf x}=\tfrac{x_1-x_2}{2}(1,-1,0)

, which lies along

\mathbf w_3

. The lost quantity is the difference

x_1-x_2

, with score

z_3=\tfrac{x_1-x_2}{\sqrt2}

:

\operatorname{Var}(z_3)=\frac{\operatorname{Var}x_1+\operatorname{Var}x_2-2\operatorname{Cov}(x_1,x_2)}{2}=\frac{4+4-4}{2}=2=\lambda_3\ \checkmark

PCA kept the sum of the correlated pair and dropped their difference — the small, quiet part of how they move together. And

z_2

is simply

x_3

: PCA only mixes variables that actually move together.

answers at a glance: $x_3$ is uncorrelated with the others, so $C$ is block-diagonal; $\lambda=6,\ 3,\ 2$ ; $\mathbf w_1=\tfrac1{\sqrt2}(1,1,0)$ , $\mathbf w_2=(0,0,1)$ , $\mathbf w_3=\tfrac1{\sqrt2}(1,-1,0)$ ; $z_1=(x_1+x_2)/\sqrt2$ , spread $6$ ; keeping two loses $x_1-x_2$ , spread $2=\lambda_3$ .

Problem 5medium

A gene study records $D=12{,}000$ genes on $N=40$ tissue samples. The centred $X$ is $40\times12{,}000$ and $C=\tfrac1N X^\top X$ . (a) Give the size of $C$ and the memory it needs in 8-byte numbers, and explain why a direct eigen-split is impractical. (b) Show that if $C\mathbf w=\lambda\mathbf w$ , then $\mathbf u=X\mathbf w$ satisfies $K\mathbf u=\lambda\mathbf u$ with $K=\tfrac1N XX^\top$ . Give the size of $K$ . (c) From an eigenvector $\mathbf u$ of $K$ , recover the eigenvector of $C$ , with the rescaling it needs. What is the largest possible number of non-zero eigenvalues of $C$ ?

What this tests. What changes when there are more columns than rows. How to attack it. Sizes first: the covariance matrix is always (features) × (features). The derivation is one move: multiply the eigen-equation on the left by $X$ and regroup. A proportionality is not an answer until you rescale, and centring costs one dimension.

Show the full solution

(a) Size.

C

is

12{,}000\times12{,}000=1.44\times10^8

entries.

1.44\times10^8\times8=1.152\times10^9\ \text{bytes}\approx1.152\ \text{GB}.

Storage is the smaller problem. An eigen-split costs about

D^3=1.728\times10^{12}

operations — hours of work to find structure in only 40 samples.

(b) The small problem. Multiply

\tfrac1N X^\top X\mathbf w=\lambda\mathbf w

on the left by

X

:

\frac1N XX^\top(X\mathbf w)=\lambda(X\mathbf w)\quad\Longrightarrow\quad K\mathbf u=\lambda\mathbf u,\qquad \mathbf u=X\mathbf w.

K

is

N\times N=40\times40

:

1{,}600

entries instead of

1.44\times10^8

, and the eigenvalue

\lambda

is the same.

(c) Back to genes. Multiply

K\mathbf u=\lambda\mathbf u

on the left by

X^\top

:

\frac1N X^\top X(X^\top\mathbf u)=\lambda(X^\top\mathbf u)\ \Longrightarrow\ C(X^\top\mathbf u)=\lambda(X^\top\mathbf u),\qquad \mathbf w=\frac{X^\top\mathbf u}{\|X^\top\mathbf u\|}.

Count:

\operatorname{rank}X\le\min(N,D)=40

, and centring makes the 40 rows add to zero, so

\operatorname{rank}C\le N-1=39

. At most 39 of the 12,000 eigenvalues are non-zero, and

K

holds all of them.

answers at a glance: $C$ is $12{,}000\times12{,}000$ , $\approx1.152$ GB, eigen-split $\sim1.7\times10^{12}$ operations; $K=\tfrac1N XX^\top$ is $40\times40$ with the same $\lambda$ ; $\mathbf w=X^\top\mathbf u/\|X^\top\mathbf u\|$ ; at most $39$ non-zero eigenvalues.

Problem 6easy

The covariance matrix of a five-variable dataset has eigenvalues $4.5,\ 2.1,\ 0.9,\ 0.4,\ 0.1$ . (a) Give the total spread and $\operatorname{tr}C$ . (b) Find the share kept by the first two components, and the smallest number of components that keeps at least $90\%$ . (c) With $W$ holding all five unit eigenvectors and $Z=XW$ , show that $\operatorname{Cov}(Z)$ is diagonal and name its diagonal. What does that say about the components?

What this tests. Eigenvalues as a spread budget, and why components never repeat each other. How to attack it. (a) is the trace identity — one line. In (b) build the running total once and read both answers off it. (c) is three lines using $CW=W\Lambda$ and $W^\top W=I$ .

Show the full solution

(a) The budget. Turning the axes never changes the total spread:

\operatorname{tr}C=\sum_d\lambda_d=4.5+2.1+0.9+0.4+0.1=8.0.

(b) Shares.

component	1	2	3	4	5
$\lambda_d$	4.5	2.1	0.9	0.4	0.1
share	56.25 %	26.25 %	11.25 %	5.00 %	1.25 %
running total	56.25 %	82.50 %	93.75 %	98.75 %	100 %

The first two keep

6.6/8.0=82.5\%

. Two fall short of

90\%

; three reach

93.75\%

. So

M=3

.

(c) Uncorrelated.

Z

is centred because

X

is, so

\begin{aligned}\operatorname{Cov}(Z)&=\frac1N(XW)^\top(XW)=W^\top CW=W^\top W\Lambda\\ &=\Lambda=\operatorname{diag}(4.5,\,2.1,\,0.9,\,0.4,\,0.1).\end{aligned}

Every off-diagonal entry is zero: no two components move together. The diagonal says once more that the spread of component

d

is

\lambda_d

. In practice the scores can go straight into a regression with no twin-column trouble.

answers at a glance: total $=\operatorname{tr}C=8.0$ ; first two keep $82.5\%$ ; $M=3$ ( $93.75\%$ ); $\operatorname{Cov}(Z)=\operatorname{diag}(4.5,2.1,0.9,0.4,0.1)$ — uncorrelated components, each with spread $\lambda_d$ .

Problem 7medium

A centred data matrix has $N=100$ rows, $D=4$ columns and singular values $20,\ 10,\ 5,\ 1$ . (a) Find the eigenvalues of $C=\tfrac1N X^\top X$ , and say where the principal directions sit in $X=U\Sigma V^\top$ . (b) Find the share kept by the first two components and the smallest number that keeps at least $95\%$ . (c) Write the best rank-2 copy of $X$ and its error in the spectral and the Frobenius norm.

What this tests. The SVD route and the best low-rank copy. How to attack it. One formula does (a): $\lambda=\sigma^2/N$ . The directions sit in the factor whose rows are indexed by features. (c) is Eckart–Young: cut the SVD, and the error is built from the singular values you dropped.

Show the full solution

(a) Eigenvalues.

C=V\,\tfrac{\Sigma^2}{N}\,V^\top

, so

\lambda_d=\sigma_d^2/N

:

\lambda_1=\frac{400}{100}=4,\quad \lambda_2=\frac{100}{100}=1,\quad \lambda_3=\frac{25}{100}=0.25,\quad \lambda_4=\frac{1}{100}=0.01.

The directions are the columns of

V

: with points in rows,

V

has

D=4

rows and lives in feature space. (With points in columns, as on the slides, they would be the columns of

U

.)

(b) Shares. Total

=4+1+0.25+0.01=5.26

. The first alone keeps

4/5.26=76.05\%

, short of

95\%

. The first two keep

5/5.26=95.06\%

, which clears it. So

M=2

.

(c) Eckart–Young. Cut after two layers:

\tilde X_2=U_2\Sigma_2V_2^\top=\sigma_1\mathbf u_1\mathbf v_1^\top+\sigma_2\mathbf u_2\mathbf v_2^\top=20\,\mathbf u_1\mathbf v_1^\top+10\,\mathbf u_2\mathbf v_2^\top.

The error is made only of the dropped layers:

\|X-\tilde X_2\|_2=\sigma_3=5,\qquad \|X-\tilde X_2\|_F=\sqrt{5^2+1^2}=\sqrt{26}\approx5.10.

No rank-2 matrix gets closer.

answers at a glance: $\lambda=4,\ 1,\ 0.25,\ 0.01$ ; directions = columns of $V$ ; total $5.26$ ; first two keep $95.06\%$ (first alone $76.05\%$ ), so $M=2$ ; $\tilde X_2=20\mathbf u_1\mathbf v_1^\top+10\mathbf u_2\mathbf v_2^\top$ ; errors $5$ (spectral) and $\sqrt{26}\approx5.10$ (Frobenius).

Problem 8medium

The slides' nine-point example. Two variables are measured on nine items:

	1	2	3	4	5	6	7	8	9
$x_1$	1.11	1.21	1.36	1.49	1.63	1.68	1.83	1.88	1.95
$x_2$	10	12	13	15	16	17	18	19	20

After centring, the covariance matrix (divided by $N=9$ ) is $C=\begin{bmatrix}0.0794988&0.8882716\\0.8882716&10.0246914\end{bmatrix}$ . (a) Find the means and $\lambda_1$ . (b) Find the unit direction $\mathbf w_1$ . (c) Find the scores of the first three items, and rebuild item 1 in the original units. (d) $\mathbf w_1$ is almost exactly the $x_2$ axis. Is that because $x_2$ matters more? What would standardising change?

What this tests. The recipe on unfriendly decimals, and the unit trap in a real example. How to attack it. Use the trace and determinant to get $\lambda$ from the quadratic formula; build the eigenvector from one row of $C-\lambda I$ ; keep five or six decimals until the end.

Show the full solution

(a) Means and $\lambda_1$ .

\mu_1=\tfrac{14.14}{9}=1.571111

and

\mu_2=\tfrac{140}{9}=15.555556

. For a

2\times2

matrix,

\lambda^2-(\operatorname{tr}C)\lambda+\det C=0

:

\begin{aligned}\operatorname{tr}C&=0.0794988+10.0246914=10.1041901,\\ \det C&=0.0794988\times10.0246914-0.8882716^2=0.0079241,\\ \lambda_1&=\frac{10.1041901+\sqrt{10.1041901^2-4(0.0079241)}}{2}=10.103406.\end{aligned}

The other root is

\lambda_2=10.1041901-10.103406=0.000784

. The first component keeps

99.99\%

.

(b) The direction. The first row of

(C-\lambda_1I)\mathbf w=\mathbf 0

reads

(0.0794988-10.103406)a+0.8882716\,b=0

, so

b=11.284\,a

. Take

a=1

:

(1,\ 11.2847)

, of length

11.3289

. Divide:

\mathbf w_1\approx(0.08827,\ 0.99610).

(c) Scores. Centre each item, then

z=0.08827\,x_1+0.99610\,x_2

:

\begin{aligned}z_1&=0.08827(-0.461111)+0.99610(-5.555556)=-5.5746,\\ z_2&=0.08827(-0.361111)+0.99610(-3.555556)=-3.5736,\\ z_3&=0.08827(-0.211111)+0.99610(-2.555556)=-2.5642.\end{aligned}

These match the slides'

-5.57,\ -3.57,\ -2.56

. Rebuild item 1:

z_1\mathbf w_1=(-0.4921,\ -5.5528)

; add the mean back:

(1.0790,\ 10.0027)

— very close to the original

(1.11,\ 10)

.

(d) The unit trap, in the wild. No.

x_2

's spread (

10.02

) is about

126

times

x_1

's (

0.0795

), simply because of the units the two were written in. PCA chases spread, so it follows

x_2

. The two columns are in fact almost perfectly related: their correlation is

0.8882716/\sqrt{0.0794988\times10.0246914}=0.9950

. Standardise, and

C

becomes

\begin{bmatrix}1&0.9950\\0.9950&1\end{bmatrix}

: now

\mathbf w_1=\tfrac1{\sqrt2}(1,1)

, an equal mix, with

\lambda_1=1.9950

out of

2

.

answers at a glance: $\boldsymbol\mu=(1.571111,\ 15.555556)$ ; $\lambda_1=10.1034$ ( $\lambda_2=0.000784$ , $99.99\%$ ); $\mathbf w_1\approx(0.0883,\ 0.9961)$ ; scores $-5.5746,\ -3.5736,\ -2.5642$ ; item 1 rebuilt as $(1.0790,\ 10.0027)$ ; standardised: correlation $0.9950$ , $\mathbf w_1=\tfrac1{\sqrt2}(1,1)$ , $\lambda_1=1.9950$ .

Problem 9medium

Run power iteration on $C=\begin{bmatrix}5&2\\2&8\end{bmatrix}$ from $\mathbf x_0=(1,0)$ . (a) Compute $\mathbf x_1$ and $\mathbf x_2$ . (b) The true top direction is $\tfrac1{\sqrt5}(1,2)$ , at $63.43^\circ$ . Find the angle of each $\mathbf x_k$ to it and show the tangent of that angle shrinks by $\lambda_2/\lambda_1$ each pass. (c) Estimate $\lambda_1$ from $\mathbf x_2$ with $\mathbf x_2^\top C\mathbf x_2$ . (d) How many passes until the arrow is within $1^\circ$ of the answer?

What this tests. Running the loop by hand, and the rate it closes in. How to attack it. You may skip the rescaling in the middle — it never changes the direction — and rescale only when you need an actual unit vector.

Show the full solution

(a) Two passes.

C\mathbf x_0=(5,2)

, length

\sqrt{29}=5.3852

, so

\mathbf x_1=(0.92848,\ 0.37139)

. Next, work with the unscaled vector:

C(5,2)=(29,\ 26)

, length

\sqrt{1517}=38.9487

, so

\mathbf x_2=(0.74457,\ 0.66755)

.

(b) The angle. The eigenvalues are

9

and

4

, so

\lambda_2/\lambda_1=4/9

. The start is at

0^\circ

,

\mathbf x_1

at

21.80^\circ

,

\mathbf x_2

at

41.88^\circ

. Measured from

63.43^\circ

:

\begin{aligned}\tan63.43^\circ&=2,\\ \tan(63.43^\circ-21.80^\circ)&=\tan41.63^\circ=0.8889=2\times\tfrac49,\\ \tan(63.43^\circ-41.88^\circ)&=\tan21.56^\circ=0.3951=2\times\big(\tfrac49\big)^2.\end{aligned}

Exactly as the eigen-expansion predicts: the wrong part shrinks by

4/9

each pass.

(c) Estimate $\lambda_1$ .

\mathbf x_2^\top C\mathbf x_2=5(0.74457)^2+2\cdot2(0.74457)(0.66755)+8(0.66755)^2=8.3250

, about

7.5\%

below

9

. Its error is

(\lambda_1-\lambda_2)\sin^2\theta_2=5\sin^2 21.56^\circ=0.675

, and because it goes with

\sin^2\theta

it shrinks by about

(4/9)^2

per pass — twice as fast as the angle, on a log scale.

(d) Within $1^\circ$ . Need

2\,(4/9)^k<\tan1^\circ=0.017455

, so

k>\dfrac{\ln(0.0087275)}{\ln(4/9)}=5.85

. Six passes: the angle is then

0.88^\circ

(after five it is still

1.99^\circ

).

answers at a glance: $\mathbf x_1=(0.9285,\ 0.3714)$ , $\mathbf x_2=(0.7446,\ 0.6675)$ ; angles to $\mathbf w_1$ : $63.43^\circ\to41.63^\circ\to21.56^\circ$ , tangents $2\to0.889\to0.395$ (ratio $4/9$ ); estimate $\lambda_1\approx8.3250$ ; $6$ passes for $1^\circ$ .

Problem 10medium

A three-feature PCA has $\operatorname{tr}C=10$ . Keeping only PC1, the average squared rebuild error over the training data is $4.0$ . Keeping PC1 and PC2, it is $1.0$ . (a) Recover $\lambda_1,\lambda_2,\lambda_3$ . (b) Give each component's share, and the smallest $M$ that keeps at least $95\%$ . (c) A new centred point has scores $(z_1,z_2,z_3)=(2,\ -1,\ 0.5)$ . Find its squared rebuild error when keeping one component, and when keeping two.

What this tests. The rebuild-error view, asked backwards. How to attack it. The average error is the sum of the dropped eigenvalues, and the trace is the sum of all of them. For a single point, the error is the sum of its squared dropped scores.

Show the full solution

(a) Read the eigenvalues off the errors. Keeping two, the error is the one dropped eigenvalue:

\lambda_3=1.0

. Keeping one, it is the two dropped:

\lambda_2+\lambda_3=4.0

, so

\lambda_2=3.0

. The trace gives the rest:

\lambda_1=10-4=6.0

. Check the order:

6\ge3\ge1

✓.

(b) Shares.

6/10=60\%

,

3/10=30\%

,

1/10=10\%

. Running totals

60\%,\ 90\%,\ 100\%

. Two components keep

90\%

, short of

95\%

, so

M=3

— which means keeping everything. A

95\%

target is too strict for this data.

(c) One point. The directions are orthonormal, so

\|\mathbf x\|^2=z_1^2+z_2^2+z_3^2=4+1+0.25=5.25

, and each kept direction keeps exactly its

z^2

.

\text{keep 1: }z_2^2+z_3^2=1+0.25=1.25,\qquad \text{keep 2: }z_3^2=0.25.

This point loses less than the average (

4.0

and

1.0

); a single point can land anywhere, only the average is fixed by the eigenvalues.

answers at a glance: $\lambda=6,\ 3,\ 1$ ; shares $60\%,\ 30\%,\ 10\%$ ; $M=3$ for $95\%$ ; the point loses $1.25$ keeping one and $0.25$ keeping two.

Problem 11medium

Three analysts each propose the first two loadings of a three-feature PCA:

A: $\ \mathbf a=\tfrac13(2,\,1,\,2)$ and $\mathbf b=\tfrac1{\sqrt5}(1,\,-2,\,0)$
B: $\ \mathbf a=(0.6,\ 0.8,\ 0)$ and $\mathbf b=(0,\ 0.6,\ 0.8)$
C: $\ \mathbf a=\tfrac13(1,\,2,\,2)$ and $\mathbf b=(2,\,1,\,-2)$

(a) Run the two checks on each pair and say which could really be principal components. (b) For the valid pair, find the third direction. (c) Repair the pair that fails only one check. (d) With the valid pair kept, find the scores and the squared rebuild error of the centred point $\mathbf x=(3,\ 0,\ 3)$ , and confirm the error with the third direction.

What this tests. The two checks every set of loadings must pass, and using them. How to attack it. Length 1: add the squares. Right angles: the dot product must be zero. In three dimensions, the direction at right angles to two others is their cross product, rescaled.

Show the full solution

(a) The audit.

pair	$\\|\mathbf a\\|^2$	$\\|\mathbf b\\|^2$	$\mathbf a^\top\mathbf b$	verdict
A	$\tfrac{4+1+4}{9}=1$	$\tfrac{1+4+0}{5}=1$	$\tfrac{2-2+0}{3\sqrt5}=0$	valid
B	$0.36+0.64=1$	$0.36+0.64=1$	$0+0.48+0=0.48$	not at right angles
C	$\tfrac{1+4+4}{9}=1$	$4+1+4=9$	$\tfrac{2+2-4}{3}=0$	$\mathbf b$ has length 3

Only A passes both checks.

(b) The third direction. Cross product of

(2,1,2)

and

(1,-2,0)

:

\begin{gathered}(1\cdot0-2\cdot(-2),\ 2\cdot1-2\cdot0,\ 2\cdot(-2)-1\cdot1)=(4,\ 2,\ -5),\\ \text{length }\sqrt{45}=3\sqrt5.\end{gathered}

So

\mathbf c=\tfrac1{3\sqrt5}(4,2,-5)

. Check:

(8+2-10)=0

and

(4-4+0)=0

✓.

(c) Repair C. Its only fault is the length of

\mathbf b

. Divide by 3:

\mathbf b=\tfrac13(2,1,-2)

, length 1, still at right angles to

\mathbf a

. (B cannot be repaired by rescaling — the angle is wrong.)

(d) One point.

z_1=\mathbf a^\top\mathbf x=\tfrac{6+0+6}{3}=4

and

z_2=\mathbf b^\top\mathbf x=\tfrac{3-0+0}{\sqrt5}=1.3416

. Then

\|\mathbf x\|^2-z_1^2-z_2^2=18-16-1.8=0.2.

Along

\mathbf c

:

z_3=\tfrac{12+0-15}{3\sqrt5}=-\tfrac1{\sqrt5}

, and

z_3^2=0.2

✓.

answers at a glance: only A is valid (B has $\mathbf a^\top\mathbf b=0.48$ ; C's $\mathbf b$ has length 3); third direction $\tfrac1{3\sqrt5}(4,2,-5)$ ; C repaired as $\tfrac13(2,1,-2)$ ; for $(3,0,3)$ : $z_1=4$ , $z_2=1.3416$ , error $0.2=z_3^2$ .

Problem 12hard

A tiny "wide" dataset: $N=3$ points, $D=4$ features, already centred:

X=\begin{bmatrix}1&2&0&1\\0&-1&1&-2\\-1&-1&-1&1\end{bmatrix}.

(a) Check that $X$ is centred, and build $K=\tfrac1N XX^\top$ . (b) Find the eigenvalues of $K$ and unit eigenvectors. (c) Recover the first principal direction $\mathbf w_1=X^\top\mathbf u_1/\|X^\top\mathbf u_1\|$ and check that $\|X^\top\mathbf u_1\|=\sqrt{N\lambda_1}$ . (d) Confirm $C\mathbf w_1=\lambda_1\mathbf w_1$ directly with $C=\tfrac1N X^\top X$ , recover $\mathbf w_2$ , and explain why $C$ ( $4\times4$ ) has only two non-zero eigenvalues.

What this tests. The Gram trick on actual numbers. How to attack it. $K$ 's entries are dot products between rows. Its rows add to zero (because the data is centred), so $(1,1,1)$ is always an eigenvector with eigenvalue $0$ . Guess the others from the pattern, then check.

Show the full solution

(a) Centred, and $K$ . Column sums:

1+0-1=0

,

2-1-1=0

,

0+1-1=0

,

1-2+1=0

✓. The row dot products are

\mathbf r_1\cdot\mathbf r_1=6

,

\mathbf r_2\cdot\mathbf r_2=6

,

\mathbf r_3\cdot\mathbf r_3=4

,

\mathbf r_1\cdot\mathbf r_2=-4

,

\mathbf r_1\cdot\mathbf r_3=-2

,

\mathbf r_2\cdot\mathbf r_3=-2

:

K=\frac13\begin{bmatrix}6&-4&-2\\-4&6&-2\\-2&-2&4\end{bmatrix}.

(b) Eigenvalues of $K$ . Try the patterns.

XX^\top(1,-1,0)=(10,-10,0)

, eigenvalue

10

.

XX^\top(1,1,-2)=(6,6,-12)

, eigenvalue

6

.

XX^\top(1,1,1)=(0,0,0)

, eigenvalue

0

. Divide by

N=3

:

\begin{gathered}\lambda_1=\tfrac{10}{3}\approx3.3333,\quad \lambda_2=2,\quad \lambda_3=0,\\ \mathbf u_1=\tfrac1{\sqrt2}(1,-1,0),\qquad \mathbf u_2=\tfrac1{\sqrt6}(1,1,-2).\end{gathered}

Check:

\tfrac{10}{3}+2+0=\tfrac{16}{3}=\operatorname{tr}K

✓.

(c) Back to four features.

X^\top(1,-1,0)=\mathbf r_1-\mathbf r_2=(1,\ 3,\ -1,\ 3)

, length

\sqrt{20}

. With the unit

\mathbf u_1

this is

\tfrac1{\sqrt2}(1,3,-1,3)

, length

\sqrt{10}

, and indeed

\sqrt{N\lambda_1}=\sqrt{3\cdot\tfrac{10}{3}}=\sqrt{10}

✓.

\mathbf w_1=\frac{1}{2\sqrt5}(1,\ 3,\ -1,\ 3)\approx(0.2236,\ 0.6708,\ -0.2236,\ 0.6708).

(d) Direct check. The column dot products give

X^\top X=\begin{bmatrix}2&3&1&0\\3&6&0&3\\1&0&2&-3\\0&3&-3&6\end{bmatrix},\qquad X^\top X\,(1,3,-1,3)=(10,\ 30,\ -10,\ 30).

That is

10\,(1,3,-1,3)

, so

C\mathbf w_1=\tfrac{10}{3}\mathbf w_1

✓ — the same

\lambda_1

. Second direction:

X^\top(1,1,-2)=\mathbf r_1+\mathbf r_2-2\mathbf r_3=(3,3,3,-3)

, length

6

, so

\mathbf w_2=\tfrac12(1,1,1,-1)

, with

\lambda_2=2

and

\mathbf w_1^\top\mathbf w_2=\tfrac1{4\sqrt5}(1+3-1-3)=0

✓. Three centred points span at most

N-1=2

dimensions, so the other two eigenvalues of

C

are

0

:

\operatorname{tr}C=\tfrac{2+6+2+6}{3}=\tfrac{16}{3}=\tfrac{10}{3}+2

✓.

answers at a glance: $K=\tfrac13\begin{bmatrix}6&-4&-2\\-4&6&-2\\-2&-2&4\end{bmatrix}$ ; $\lambda=\tfrac{10}{3},\ 2,\ 0$ ; $\mathbf w_1=\tfrac1{2\sqrt5}(1,3,-1,3)$ , $\|X^\top\mathbf u_1\|=\sqrt{10}=\sqrt{N\lambda_1}$ ; $\mathbf w_2=\tfrac12(1,1,1,-1)$ ; only $N-1=2$ non-zero eigenvalues.

Next up

Unit 13 · Support Vector Machines →

PCA asked for the direction of widest spread; Unit 13 asks for the widest street between two groups of points — another geometric wish that becomes a constrained optimisation with a fine for every point. You already built a two-point version at the end of Unit 11; now it grows into a full classifier, and its dual sees the data only through a Gram matrix of dot products.

← All units