A data set with many numerical features often has most of its variation along a few directions. Principal component analysis (PCA) finds an orthonormal set of directions, ordered by how much of the sample variation they carry, and uses the first few to describe each observation by a short vector. It is used for compression, for visualization in two or three coordinates, and as a preprocessing step before clustering or classification. This unit builds on the centroid and squared-error viewpoint of k-means and on the whitening unit, which already used the covariance matrix; here we derive PCA from a single optimization problem and prove what it does and does not guarantee.
Centered data and the covariance matrix
Definition 13.1.1
(Sample mean, centered data and sample covariance)
Let be observations, . The sample mean is , and the centered observations are , which satisfy . The sample covariance matrix is
It is symmetric and positive semidefinite, because for every . Here we divide by ; dividing by multiplies every eigenvalue by the same constant and changes no eigenvector.
For a unit vector , the number is the coordinate of observation along after centering, and the quantity is the sample variance of these coordinates. The spectral theorem gives an orthonormal basis of eigenvectors, , with .
Definition 13.1.2
(Principal components, scores and explained variance)
The unit eigenvectors of , ordered by eigenvalue, are the principal directions (loadings). The score of observation on component is . The eigenvalue is the variance of component . The proportion of variance explained by the first components is
where the denominator is . If eigenvalues repeat, the directions inside a repeated eigenspace are not unique, and every sign is equally valid.
What PCA optimizes
Theorem 13.1.3
(Variance maximization and best rank-k reconstruction)
Let have eigenpairs as above and let .
- , attained at .
- For , , attained at .
- The score vectors of different components are uncorrelated: .
- Among all matrices with orthonormal columns, the mean squared reconstruction error is minimized by , and its minimum is .
Proof
(Proof of the variance and reconstruction statements)
Write a unit vector as with . Then , a weighted average of the eigenvalues, so it is at most , with equality at . If , then , and the same average is at most . This proves parts 1 and 2.
For part 3, , which is if and otherwise.
For part 4, the Pythagorean identity gives , because is an orthogonal projection. Averaging over , the error equals . So minimizing error is the same as maximizing over orthonormal columns of . Let ; then with and . A weighted sum with , is largest when the weight sits on the largest eigenvalues, giving , attained when spans . The minimum error is therefore .
Proof X-ray
Where the reconstruction bound is really proved
The proof of part 4 has two moves, and only the second is non-routine. The first reduces the error to a trace: it uses that the columns of are orthonormal, so that is an orthogonal projection and the Pythagorean identity applies. With non-orthonormal columns that identity fails and the formula is no longer the error.
The second move changes the unknown from a matrix to the numbers . Two facts about a projection constrain them: , and . The closing step is a comparison. Since for and for ,
Each inequality uses the sign of or of , and the final zero is exactly the constraint . Equality holds when for , that is, when spans . If other subspaces also reach equality, so the minimizer is then not unique.
Part 4 explains why PCA is the natural companion of the squared-error objective of k-means: it chooses the -dimensional subspace through the mean that leaves the least squared distance between data and their projections. It makes no use of class labels, so a direction of large variance need not be a direction that separates classes.
Concept lensGeometric
Principal directions as the axes of the covariance ellipsoid
Suppose is invertible and consider . Writing turns the condition into , an ellipsoid whose axes lie along with semi-axis lengths . So the principal directions are exactly the axes of this ellipsoid, and part 1 says the first one is the longest. In the first worked example the axes point along and with lengths and . Equal eigenvalues give a round cross-section, which is why their directions are not unique.
The procedure
- Compute and the centered data. 2. Form . 3. Find its eigenvalues and orthonormal eigenvectors. 4. Choose , for instance the smallest whose explained-variance proportion reaches a chosen level. 5. Report scores , and reconstruct . Termination and cost are those of a symmetric eigenproblem, roughly for the dense method.
Worked examples
Worked example 13.1.4
(A two-dimensional data set computed exactly)
Take four observations . The mean is , and the centered points are . Then
The characteristic polynomial has trace and determinant , so and . Since and , the unit directions are and .
The scores on are , whose mean square is , as predicted. The scores on are , mean square . The proportion explained by the first component is . Reconstructing from one component gives the third point as against the actual ; the squared error is . The squared errors of the four points are , with mean , confirming part 4.
Worked example 13.1.5
(Explained variance, and the effect of units)
Suppose a three-feature data set has already-centered covariance
The matrix is block diagonal. The upper block has eigenvalues , namely and , with directions and ; the last block gives with direction . The proportions of variance are for one component and for two. The two-component mean squared reconstruction error is .
Now express the third feature in units ten times smaller, replacing it by times its value. Its variance becomes and the covariance matrix is block diagonal with in the last place. The top eigenvalue is with direction , and one component now explains of the variance. Nothing about the underlying phenomenon changed; only the unit did.
Worked example 13.1.6
(Degenerate cases: collinear data and an isotropic cloud)
First take the three observations , which lie on a line. The mean is and the centered points are , so
The trace is and the determinant is , so the eigenvalues are and . Since , the first direction is . The scores on are with mean square , as predicted. One component explains of the variance, and the reconstruction error for is : every point is reproduced exactly. The zero eigenvalue is legitimate; is only positive semidefinite.
Now take , already centered. Then , so and every unit vector is an eigenvector. The direction gives scores with mean square , and so does . The explained proportion of one component is whichever direction is chosen; "the first principal direction" is not determined here.
Common mistakes and subtle points
Common mistake
(PCA is not invariant to feature scaling, and it needs centering)
Because depends on the units of each feature, features measured on large scales dominate the first components, as in the second example. When features have incompatible units it is common to standardize each feature first, which amounts to using the correlation matrix; this is a modeling decision, not a free correction. Omitting the subtraction of gives eigenvectors of , which in general differ from principal directions and are dominated by the location of the data.
Further points. A component with high variance is not necessarily predictive of a label. Signs and repeated-eigenvalue directions are arbitrary, so statements about "the" direction hold only up to these ambiguities. In a train and test setting, the mean and the eigenvectors are computed from the training data only and then applied to test observations. Finally, scores are uncorrelated, which is weaker than independent; the whitening unit discusses the difference.
Counterexample mode
The largest-variance direction need not separate the classes
A tempting claim is that the first principal direction is the best direction for telling two classes apart. Take class A to be and class B to be . The mean is , so the data are centered and
The first principal direction is , with variance . The coordinates of the two classes along are identical, namely and in both, so this direction gives no information about the class. The direction , with the small variance , gives coordinate for every point of A and for every point of B, and separates the classes perfectly. PCA never sees the labels; what it maximizes is variance, so using it before a classifier is a modeling choice that needs supporting evidence from the data.
Exercises
Quick check
(1. Compute the first principal direction)
The centered observations are . Find , its eigenvalues, the first principal direction and the proportion of variance it explains.
Solution · Solution 1
. Its eigenvalues are and , the first direction is up to sign, and it explains of the variance.
Quick check
(2. Choose the number of components)
A data set has covariance eigenvalues . Find the explained proportion for , the smallest reaching , and the mean squared reconstruction error for .
Solution · Solution 2
The total is . The proportions are , and . The smallest reaching is , since is not below the target. For the error is the sum of the discarded eigenvalues, .
Quick check
(3. Prove that scores are uncorrelated)
Let be eigenvectors of for different eigenvalues with . Show that the score vectors on these components have zero sample covariance.
Solution · Solution 3
The scores are centered, since . Their sample covariance is , because eigenvectors of a symmetric matrix for different eigenvalues are orthogonal.
Quick check
(4. Reconstruct a new point)
Use the first worked example with one component. Reconstruct the new observation and compute its squared reconstruction error.
Solution · Solution 4
Center it with the training mean: . Its score on is , so the reconstruction is . The residual is , with squared norm . This equals the squared score on , namely .