Principal Component Analysis

Main idea

PCA finds the directions in which data spreads out most, and they turn out to be the eigenvectors of its covariance matrix, because the spread along a direction is a quadratic form. Keeping only the top few directions lets you describe the data with fewer numbers while keeping most of what makes the points different.

{\htmlData{sym=0}{S}} = \frac{1}{N - 1}{\htmlData{sym=1}{B}}{\htmlData{sym=1}{B}}^T, \qquad {\htmlData{sym=0}{S}}\vec u_i = {\htmlData{sym=2}{\lambda_i}}\vec u_i

What the symbols mean

$S$
Covariance matrix
Symmetric; entry (i, j) measures how variables i and j vary together.
$B$
Centered data
Each column is one observation with the mean subtracted.
$\lambda_i$
Variance along u_i
How much of the data's spread lies in that direction.

Explanation

Principal component analysis, or PCA, is simply a way to find the directions along which a cloud of data points is most spread out, so you can describe the data with fewer numbers. "Principal" here means main or most important, and the "components" are those directions, ranked from most spread to least. What it's good for: shrinking data with dozens or thousands of variables down to the few directions that actually matter, so you can compress it, speed up machine learning or plot it in 2D. All we're really saying here is that $S = \frac{1}{N - 1}BB^T$ (the covariance matrix) records how the variables spread: its diagonal entries are each variable's variance, and its off-diagonal entries say how two variables move together. Then $S\vec u_i = \lambda_i\vec u_i$ says the eigenvectors $\vec u_i$ are the directions and the eigenvalues $\lambda_i$ are how much spread lies along each one. Every piece is something from earlier in this unit; bear with the setup.

Think about why eigenvectors show up. The variance of the data along a unit direction $\vec u$ works out to $\vec u^TS\vec u$ , which is a quadratic form. From the quadratic forms lesson, its largest value over unit vectors is the largest eigenvalue of $S$ , reached along the top eigenvector. And since $S$ is symmetric, the spectral theorem guarantees the principal components are perpendicular to each other.

A common mistake. It's tempting to skip subtracting the mean, because the data looks fine as it is. It isn't safe: without centering, $BB^T$ measures spread around the origin instead of around the data's center, and the first "component" mostly just points from the origin toward the middle of the cloud.

Steps:

Subtract the mean from each variable.
Compute the covariance matrix $S$ .
Find its eigenvalues and eigenvectors. The eigenvector with the largest eigenvalue is the first principal component: the direction of greatest spread.

Variance explained: the total variance is the trace of $S$ , the sum of the eigenvalues. The first $k$ components explain $\frac{\lambda_1 + \cdots + \lambda_k}{\lambda_1 + \cdots + \lambda_n}$ of it.

PCA is the SVD of the centered data matrix in disguise: the eigenvectors of $BB^T$ are the left singular vectors of $B$ , so software usually computes PCA with the SVD directly.

There's an animation further down that shows the spread of the data's shadows changing as a line turns through the cloud.

See it

Five centered data points and a line through their center pointing along u, with each point's shadow on the line. Notice how the variance of those shadows, uᵀSu with S = [[5, 2], [2, 2]], changes as the line turns: it peaks at 6 when u points along (2, 1), the top eigenvector of S, and bottoms out at 1 along (−1, 2). Keeping only that first direction keeps 6 of the total variance of 7, about 86%.

Worked examples

Example 1

A dataset has covariance matrix $S = \begin{bmatrix}5 & 2\\ 2 & 2\end{bmatrix}$ . Find the principal components and the variance they explain.

1
The trace is 7 and the determinant is 6, so the characteristic equation is $\lambda^2 - 7\lambda + 6 = 0$ : $\lambda = 6, 1$ .

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

Find the eigenvalues of $S = \begin{bmatrix}5 & 2\\ 2 & 2\end{bmatrix}$ .

Problem 2+5 XP

What fraction of the variance does the first principal component explain?

Problem 3+5 XP

Give the first principal component as a unit vector with positive entries.

Problem 4+5 XP

What is the total variance?

Problem 5+5 XP

Eigenvalues are 9, 0.5 and 0.5. How many components keep at least 90% of the variance?

Problem 6+5 XP

Four students' scores on two quizzes, after subtracting the class averages, are $(2, 2)$ , $(-2, -2)$ , $(1, -1)$ and $(-1, 1)$ . What fraction of the total variance does the first principal component capture?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

PCA compresses each centered data point $\vec x$ to one number, its score $z = \vec x\cdot\vec u_1$ , and reconstructs it as $z\,\vec u_1$ . For $S = \begin{bmatrix}5 & 2\\ 2 & 2\end{bmatrix}$ and the point $\vec x = (3, 1)$ , find the reconstruction error $\|\vec x - z\,\vec u_1\|$ .

Where it's used

PCA compresses genetic data, reduces image features before machine learning, finds the "eigenfaces" in face recognition, and visualizes high-dimensional data in 2D.

Linear RegressionLin Alg · Computer Science Where Can a Robot Hand Move Fast?Lin Alg · Robotics

The Singular Value Decomposition