Principal component analysis: from repeated lines to eigenvectors

Part 2 built a procedure: centre the data, find the line with the least reconstruction error, replace every point by its residue, and repeat. It ended with four open questions. Lectures 6 and 7 answer all four, and the answers together make up principal component analysis.

The procedure so far

The data set is \(\{\mathbf{x}_1, \dots, \mathbf{x}_n\}\) with \(\mathbf{x}_i \in \mathbb{R}^d\), centred. Round 1 finds

"argmax" means the argument that achieves the maximum: the vector \(\mathbf{w}\) itself, not the maximum value.

Round 2 works on the residues 2:23. These are still vectors in \(\mathbb{R}^d\): the error vectors left over after round 1.

\(C'\) is the \(d \times d\) matrix built from the residues in the same way \(C\) was built from the data 3:04.

With two lines in hand, the natural question is how \(\mathbf{w}_1\) and \(\mathbf{w}_2\) are related. Look at two dimensions first. Take centred data and its best line \(\mathbf{w}_1\), a unit vector, so its tip lies on the unit circle. Each residue \(\mathbf{x}_i - (\mathbf{x}_i^\top\mathbf{w}_1)\mathbf{w}_1\) runs from the proxy on the line to the point. A projection meets the line at a right angle, so every residue is perpendicular to \(\mathbf{w}_1\).

In two dimensions only one direction is perpendicular to \(\mathbf{w}_1\), so all the residues lie on one line through the origin. In higher dimensions they lie in the hyperplane perpendicular to \(\mathbf{w}_1\). The best line for the residues in 2-D is the line they already lie on: any other line would add error that this one avoids. That line is perpendicular to \(\mathbf{w}_1\).

The lecture does not prove the second step and leaves it as an exercise. One short argument is to write a unit vector as \(\mathbf{w} = \alpha\,\mathbf{w}_1 + \beta\,\mathbf{u}\), where \(\mathbf{u}\) is a unit vector orthogonal to \(\mathbf{w}_1\) and \(\alpha^2 + \beta^2 = 1\). Every residue has \(\mathbf{x}_i'^\top\mathbf{w}_1 = 0\), so \(\mathbf{x}_i'^\top\mathbf{w} = \beta\,\mathbf{x}_i'^\top\mathbf{u}\) and

Any component along \(\mathbf{w}_1\) (\(\alpha \neq 0\)) makes \(\beta^2 < 1\) and only shrinks the objective. So the maximizer has no \(\mathbf{w}_1\) component.

The direction of \(\mathbf{w}_2\) is fixed only up to sign 8:32. The unit vector pointing the opposite way spans the same line, and it is orthogonal to \(\mathbf{w}_1\) too.

Keep going L6 · 9:05

In 2-D the procedure must stop after two rounds: \(\mathbf{w}_2\) fits the residues exactly, so the residue of the residue is the zero vector. In 100 dimensions there may still be something left, so we continue, and each new line is orthogonal to all the previous ones. After \(d\) rounds in \(\mathbb{R}^d\):

A set of mutually perpendicular unit vectors is called orthonormal 10:52.

To see what orthonormality buys, write out the residues explicitly. After round 1 the residue of \(\mathbf{x}_1\) is \(\mathbf{x}_1 - (\mathbf{x}_1^\top\mathbf{w}_1)\mathbf{w}_1\). Round 2 subtracts that vector's own projection onto \(\mathbf{w}_2\):

The last term is zero because \(\mathbf{w}_1^\top\mathbf{w}_2 = 0\). So after two rounds the residue is the point minus its projections onto \(\mathbf{w}_1\) and onto \(\mathbf{w}_2\):

The same cancellation happens in every round, because each \(\mathbf{w}_k\) is orthogonal to all the earlier ones 14:10. After \(d\) rounds, for every \(i\):

After \(d\) rounds nothing is left L6 · 14:46

In 2-D the residue after round 2 is the zero vector, because the second line fits the lined-up residues exactly. The same happens in \(d\) dimensions after \(d\) rounds. Each round removes one component, and a vector in \(\mathbb{R}^d\) has only \(d\) independent components, here along \(\mathbf{w}_1, \dots, \mathbf{w}_d\). So every residue is \(\mathbf{0}\), which gives

In linear-algebra terms this is a change of basis. The points were written in the standard basis; now each one is written in the orthonormal basis \(\mathbf{w}_1, \dots, \mathbf{w}_d\), and its coordinates are the dot products \(\mathbf{x}_i^\top\mathbf{w}_k\). Any basis can express the data, so on its own this gains nothing 16:31. The gain comes from stopping early, in the next section.

The gain appears when the data lives in a low-dimensional linear subspace. Then the residues become zero well before \(d\) rounds. Once every residue is zero, another line adds no information, so the procedure stops there.

In the lecture's example the data is in \(\mathbb{R}^{100}\) and the residues are all zero after 3 rounds. Then we have found \(\mathbf{w}_1, \mathbf{w}_2, \mathbf{w}_3\) with

• Representatives: \(\mathbf{w}_1, \mathbf{w}_2, \mathbf{w}_3\), each in \(\mathbb{R}^{100}\). They are common to the whole data set.
• Coefficients: \([\mathbf{x}_i^\top\mathbf{w}_1,\ \mathbf{x}_i^\top\mathbf{w}_2,\ \mathbf{x}_i^\top\mathbf{w}_3] \in \mathbb{R}^3\), three numbers per point. They are specific to each data point 22:37.
• Reconstruction: the linear combination of the representatives, weighted by the point's coefficients. Here it is exact.

To put numbers on it the lecture takes \(n = 100\) points as well, so \(d = 100,\ k = 3,\ n = 100\):

Residues that become exactly zero after a few rounds may or may not happen in practice. The relevant case is data that lies approximately in a low-dimensional space. The simplest example is a 2-D cloud that no single line fits, where a 1-D representation is still good enough. Then we accept some error, and we have to decide how much error to tolerate.

Pythagoras splits each point

For any unit vector \(\mathbf{w}\), a point, its proxy \((\mathbf{x}_i^\top\mathbf{w})\mathbf{w}\) and its error vector form a right triangle. So the squared length of the point is the squared length of its projection plus the squared length of its error. This holds for any line, not only the best one:

Average over all points 26:03:

The left side is the same for every line. So a small average error and a large \(\frac1n\sum(\mathbf{x}_i^\top\mathbf{w})^2\) go together: this is the derivation of Part 2 seen as geometry. After finding a line, we can look at the size of that second term to judge how good the fit is.

Track the kept amount round by round L6 · 27:37

In round \(k\) record the value \(\frac1n\sum_i(\mathbf{x}_i^\top\mathbf{w}_k)^2\). (By the residue formula above, the residue from round \(k-1\) has the same dot product with \(\mathbf{w}_k\) as \(\mathbf{x}_i\) itself, so it does not matter which one you use.)

• The value is largest in round 1, because round 1 maximizes exactly this quantity.
• Whatever round 2 finds is smaller: if it were larger, round 1 would have found that line instead. So the values fall as \(k\) grows.
• Often they fall steeply and then flatten out close to zero, with an elbow at some \(k\) 29:17. The top \(k\) directions are the signal directions, where most of the information is. The later, tiny ones can be treated as error directions. (What "information" means is made precise in L7, as variance.)

Rule of thumb 29:50: keep the top \(k\) directions, where the values of the first \(k\) rounds add up to at least 95% of the sum over all \(d\) rounds.

This is only a rule of thumb. Without further assumptions about the data, nothing says this \(k\) is the best one. After \(d\) rounds the residues are zero, so the sum over all \(d\) rounds covers everything. The lecture does not spell out the next step, but it follows by applying the Pythagoras split once per round: that sum equals the fixed total \(\frac1n\sum\lVert\mathbf{x}_i\rVert^2\), and the average error after \(k\) rounds is the sum of the values not kept. L7 restates the rule with eigenvalues; the widget there lets you try it.

1. The algorithm at the end of L6 30:27
2. Centre the data set.
3. Find the best line \(\mathbf{w}_1\): maximize \(\mathbf{w}^\top C\mathbf{w}\) over unit vectors \(\mathbf{w}\).
4. Replace each point by its residue and find the best line for the residues. Repeat.
5. After each round compare its value \(\frac1n\sum(\mathbf{x}_i^\top\mathbf{w}_k)^2\) with the total. Stop when it becomes too small, for example once the rounds so far explain 95%.

L7 looks at the same procedure through linear algebra. The problem is \(\max_{\lVert\mathbf{w}\rVert=1}\mathbf{w}^\top C\mathbf{w}\) with \(C = \frac1n\sum\mathbf{x}_i\mathbf{x}_i^\top\), the covariance matrix (with the caveat from Part 2 that the data must be centred). Its solution is \(\mathbf{w}_1\), the eigenvector of \(C\) for the largest eigenvalue 0:45.

This comes from a general result that you may have met in a linear algebra course. The lecture calls it the Hilbert min–max theorem (standard name: the Courant–Fischer min–max theorem). It says more than this 1:54:

• The eigenvectors of \(C\) form an orthonormal basis. The orthonormal basis that our error minimization finds on centred data is exactly this eigenvector basis.
• The eigenvector for the \(k\)-th largest eigenvalue is exactly the best line found in round \(k\) 2:28.
• Equivalently 3:01, maximize the same \(\mathbf{w}^\top C\mathbf{w}\) over unit vectors that are also orthogonal to the subspace spanned by the top \(k-1\) eigenvectors. The answer is the \(k\)-th eigenvector.

The round-by-round view gives the orthogonality directly 3:37. The line found in round \(k\) is orthogonal to the earlier lines by construction, because the residues it fits are orthogonal to them.

Calling \(\mathbf{w}_k\) an eigenvector names a well-studied object, but it says little about what the eigenvalues mean. Start from \(C\mathbf{w}_1 = \lambda_1\mathbf{w}_1\) 4:43 and multiply on the left by \(\mathbf{w}_1^\top\), using \(\mathbf{w}_1^\top\mathbf{w}_1 = 1\):

The same steps work for every \(k\): \(\lambda_k = \frac1n\sum_i(\mathbf{x}_i^\top\mathbf{w}_k)^2\). This is exactly the round-\(k\) value that L6 used to decide how many rounds to run 5:51. So the falling curve of L6 is the list of eigenvalues of \(C\), from largest to smallest.

The ratio only makes sense if the eigenvalues are non-negative 7:32. They are: each \(\lambda_k\) is an average of squares. So the covariance matrix has non-negative eigenvalues, which means it is positive semidefinite, and the formula above is a proof of that.

The eigenvalue view still does not say what \(\frac1n\sum(\mathbf{x}_i^\top\mathbf{w})^2\) is 8:38. Fix any unit vector \(\mathbf{w}\), not necessarily the best line, and project the data onto it. Collect the \(n\) numbers

Squared, these are the squared lengths of the proxies. Treat them as a one-dimensional data set and compute its mean and variance.

Their mean is zero L7 · 10:08

Their variance is \(\mathbf{w}^\top C\mathbf{w}\) L7 · 12:24

So for any direction \(\mathbf{w}\), \(\mathbf{w}^\top C\mathbf{w}\) is the variance of the projected values. It is the quantity the procedure maximizes, and for an eigenvector it equals the eigenvalue.

Why we want the variance high L7 · 15:11

The lecture draws two lines through the same cloud. Projected onto the best line, the proxies are spread out. Projected onto another line, they bunch together. When proxies crowd together it becomes hard to tell the points apart, and if several land on the same spot it is impossible.

We do want compression, but the compressed representation is used downstream, for example as input to a supervised learning task. There we still need to tell one data point from another, and a badly chosen line destroys that ability. In the extreme case 15:47, all the data lies on one line and we project onto the perpendicular line instead. Every point lands on the zero vector, and the representation is useless.

In the lecture's words, "we want directions where projections do not crowd": directions where the variance of the projections is as high as possible, so the information retained is as high as possible.

Take centred heights and weights (hence the negative values). Taller people tend to be heavier, so knowing the height tells you something about the weight. Loosely speaking, the two features are not independent; the lecture is careful with that word. If each person is stored as two numbers, height and weight, one number partly repeats the other.

• First direction 18:32. Suppose the best line points along \([1, 1]\). It must have length 1, so \(\mathbf{w}_1 = [1/\sqrt2,\ 1/\sqrt2]\). With one number per person we store the coefficient \(\mathbf{x}_i^\top\mathbf{w}_1 = (\text{height} + \text{weight})/\sqrt2\).
• Second direction 19:49. The line that fits the residues is perpendicular: \(\mathbf{w}_2 = [-1/\sqrt2,\ 1/\sqrt2]\), with coefficient \((\text{weight} - \text{height})/\sqrt2\). Its negative \([1/\sqrt2, -1/\sqrt2]\) works equally well.
• Re-plot 21:02 every person using these two numbers as coordinates. The new axes are the old ones rotated by 45°. Now knowing the first coordinate says nothing about the second: as \((\text{height} + \text{weight})/\sqrt2\) increases, the other coordinate is above or below zero with no pattern.

Standard fact, not derived in the lecture: the covariance of the coordinates along two different eigenvectors is \(\frac1n\sum_i(\mathbf{x}_i^\top\mathbf{w}_j)(\mathbf{x}_i^\top\mathbf{w}_k) = \mathbf{w}_j^\top C\,\mathbf{w}_k = \lambda_k\,\mathbf{w}_j^\top\mathbf{w}_k = 0\) for \(j \neq k\). That is the precise sense of "de-correlated".

This algorithm is called principal component analysis (PCA). You may have met it in the Machine Learning Foundations course; this course starts with it because ideas that come up along the way lead to something more fundamental in machine learning. The vectors \(\mathbf{w}_1, \dots, \mathbf{w}_k\) it finds are the principal components 23:12, and the projections along them are de-correlated.

1. Principal component analysis
2. Input \(\{\mathbf{x}_1, \dots, \mathbf{x}_n\}\), \(\mathbf{x}_i \in \mathbb{R}^d\). Centre it: subtract the mean from every point.
3. Compute the covariance matrix \(C = \frac1n\sum_i\mathbf{x}_i\mathbf{x}_i^\top\).
4. Find its eigenvalues \(\lambda_1 \ge \dots \ge \lambda_d\) and orthonormal eigenvectors \(\mathbf{w}_1, \dots, \mathbf{w}_d\).
5. Choose \(k\), for example the smallest \(k\) with \(\sum_{j \le k}\lambda_j \big/ \sum_{j \le d}\lambda_j \ge 0.95\).
6. Project: represent each \(\mathbf{x}_i\) by \([\mathbf{x}_i^\top\mathbf{w}_1, \dots, \mathbf{x}_i^\top\mathbf{w}_k] \in \mathbb{R}^k\). To reconstruct, use \(\sum_{j \le k}(\mathbf{x}_i^\top\mathbf{w}_j)\,\mathbf{w}_j\).

Going from \(\mathbb{R}^d\) to \(\mathbb{R}^k\) with \(k\) much smaller than \(d\) makes PCA a dimensionality reduction technique. The essential dimension we believe the data has is \(k\) 24:23: the top \(k\) eigenvectors explain 95% of the variance in the data. That is what the 0.95 meant all along. "Information" is the amount of variance explained, and each direction counts as one dimension.

PCA finds new axes, and each new axis is a combination of the original features 24:58. The coordinate \(\mathbf{x}_i^\top\mathbf{w}_1 = \sum_j (\mathbf{w}_1)_j\,x_{ij}\) weighs the features of \(\mathbf{x}_i\) by the entries of the eigenvector; in the example above it is \((\text{height} + \text{weight})/\sqrt2\). The combinations PCA finds are de-correlated, loosely speaking independent of each other.

What comes next L7 · 26:10

The next lecture applies PCA to face images, the eigenfaces example of a simple face-recognition system. It then looks at issues with PCA and cases where it does not work well. Fixing those issues reveals what matters in a data set and leads to more foundational ideas. See Part 4.

Residue (round \(k\))

What is left of a point after removing its projections onto \(\mathbf{w}_1, \dots, \mathbf{w}_k\): \(\mathbf{x}_i - \sum_{j\le k}(\mathbf{x}_i^\top\mathbf{w}_j)\mathbf{w}_j\).

Orthonormal set

Unit vectors that are mutually perpendicular: \(\lVert\mathbf{w}_k\rVert = 1\), \(\mathbf{w}_i^\top\mathbf{w}_j = 0\) for \(i \neq j\).

Change of basis

Writing each point by its coordinates \(\mathbf{x}_i^\top\mathbf{w}_k\) in the basis \(\mathbf{w}_1, \dots, \mathbf{w}_d\) instead of the standard basis.

Compressed storage

\(dk\) numbers for \(k\) shared representatives plus \(kn\) coefficients, instead of \(dn\) raw numbers.

Elbow

The round after which the values \(\frac1n\sum(\mathbf{x}_i^\top\mathbf{w}_k)^2\) become very small.

Signal and error directions

The top directions before the elbow carry most of the information; the later ones are treated as error.

95% rule

Rule of thumb: keep the smallest \(k\) with \(\sum_{j\le k}\lambda_j / \sum_{j\le d}\lambda_j \ge 0.95\).

Eigenvector, eigenvalue of \(C\)

\(C\mathbf{w}_k = \lambda_k\mathbf{w}_k\). The \(k\)-th eigenvector is the best line of round \(k\); \(\lambda_k = \frac1n\sum(\mathbf{x}_i^\top\mathbf{w}_k)^2\).

Min–max theorem

The linear-algebra result behind "the top eigenvector maximizes \(\mathbf{w}^\top C\mathbf{w}\)" (the lecture says Hilbert; usually Courant–Fischer).

Positive semidefinite

A matrix with no negative eigenvalues. \(C\) is one, since each \(\lambda_k\) is an average of squares.

Variance of the projections

\(\frac1n\sum(\mathbf{x}_i^\top\mathbf{w})^2 = \mathbf{w}^\top C\mathbf{w}\) for centred data; PCA maximizes it.

De-correlated

Coordinates along different principal components carry no linear information about each other.

Principal components

The eigenvectors \(\mathbf{w}_1, \dots, \mathbf{w}_k\) of \(C\) with the largest eigenvalues.

Dimensionality reduction

Representing each point by \(k\) numbers instead of \(d\), here its coordinates along the top \(k\) principal components.