Linear AlgebraThe Singular Value Decomposition5 of 6
The Singular Value Decomposition · 5
PCA: Directions of Greatest Variance
When a dataset has many measurements for every point, we want to compress that cloud of data down to just one or two new directions without losing what tells the points apart.
Information Is Spread
To replace a 2D cloud of points (x1,x2) with a single number per point, we project every point perpendicularly onto a line through the middle of the cloud. How much information survives depends on how spread out the projected points are along the line: projecting along the length of the cloud spreads them as far apart as possible, while projecting across the narrow width crowds them together.
The angle of the line decides how much of the cloud's spread stays on the line.
1
Measuring Spread with the Covariance Matrix
To find the direction of greatest variance without guessing angles, we need a formula for the variance of the projections along any unit vector u, one that separates the fixed data cloud from the rotating direction u.
The Covariance Matrix
First, shift the cloud so its average sits at (0,0) by subtracting (Avg x1,Avg x2) from every point, and stack the N centered points x(1),x(2),…,x(N) as the rows of a centered data matrix X.
When u has length 1, the dot product x⋅u is the signed distance of a point's projection along the line through u. Multiplying the matrix X by u takes that dot product for every row at once, giving the column vector Xu of all N projections. Because the projections are centered at 0, their variance is the average of their squares, which we can write by taking the dot product of Xu with itself and using (Xu)T=uTXT to pull the direction u to the outside:
Spread along u=N1∑(x⋅u)2Average of squared projections=N1(Xu)T(Xu)Sum of squares as a dot product=uTCcovariance matrix(N1XTX)uSeparate data X from direction u
The matrix C=N1XTX depends only on the centered data points, and for a 2D cloud its four entries measure the horizontal spread, the vertical spread, and how the two coordinates tilt together:
Stretching the cloud horizontally or vertically increases the diagonal entries, while tilting it up and right makes the off-diagonal covariance positive, tilting it down and right makes the covariance negative, and leaving it untilted makes the quadrants cancel to zero.
In a covariance matrix, the diagonal tracks horizontal and vertical spread, while the other two entries track how the data cloud tilts across the quadrants.
2
Principal Components from Eigenvectors
Now that the variance along any unit direction u is written as the quadratic form Spread(u)=uTCu, we want to find the unit vector u that makes uTCu as large as possible.
Principal Components from Eigenvectors
Even when a real data cloud is uneven and lopsided, its covariance matrix C=N1XTX is always symmetric because the top-right entry (Avg of x1x2) and bottom-left entry (Avg of x2x1) are the exact same number. By the Spectral Theorem, any symmetric matrix C has perpendicular unit eigenvectors v1 and v2 (with eigenvalues λ1≥λ2), and pointing u straight along v1 turns Cv1 into λ1v1:
Spread(v1)=v1TCv1=v1T(λ1v1)Since Cv1=λ1v1=λ11(v1Tv1)=λ1Since v1 is a unit vector
Pointing u along the perpendicular unit eigenvector v2 gives Spread(v2)=v2TCv2=λ2, and pointing u in any direction in between gives a weighted average of λ1 and λ2:
Try rotating the unit vector u around the origin to see the variance uTCu peak at λ1 along v1 and drop to its minimum λ2 along v2,90∘ away.
Even on a lopsided data cloud, the directions of widest and narrowest spread meet at a right angle, and every other direction has a spread somewhere in between.
3
Finding Principal Components Step by Step
Let's take N=4 data points in 2D: (1,2),(3,4),(5,4), and (7,6). We want to find the direction of greatest variance v1, the share of total variance it captures, and the compressed 1D projections of the four points.
Finding Principal Components Step by Step
Text solution
Subtract the center (4,4) to form XFind the average of each coordinate across the N=4 points and subtract it from every point so the cloud is centered at (0,0):
Multiply 41XTX to get the covariance matrix CAverage the squares and products of the centered coordinates across the four rows (you might also see this divided by N−1 instead of N, which multiplies every eigenvalue by the same factor without changing the eigenvectors):
Solve for the eigenvalues λ1,λ2 and the share of varianceUse trace(C)=5+2=7 and det(C)=(5)(2)−(3)(3)=1 to write the characteristic equation and compare λ1 to the total variance λ1+λ2=trace(C):
Find the unit eigenvector v1 and project with Xv1Plug λ1≈6.85 into Cv1=λ1v1 to find the unit direction v1, then multiply X by v1 to get the four signed projection distances along that line:
So the four 2D points compress down to the single list of numbers −3.61,−0.85,+0.85,+3.61 along v1, keeping 98% of the total spread in the cloud.
4
PCA and the SVD
When we want to plot our compressed 1D projections as points back in the original space, or when we already have the Singular Value Decomposition X=UΣVT of the centered data matrix, we can read off the principal components and the compressed data matrix directly from the SVD.
PCA and the SVD
Because the right singular vectors v1,v2,… in X=UΣVT are the unit eigenvectors of XTX with eigenvalues σ12,σ22,…, dividing XTX by N to form C=N1XTX leaves the eigenvectors untouched and divides each eigenvalue by N:
principal directions(columns of V)v1,v2,…variance along vifrom singular value σiλi=Nσi2
−2
2
−2
2
x1
x2
Xv1
−3.61
−0.85
+0.85
+3.61
0
×v1T
line through v1
−3.61
−0.85
+0.85
+3.61
Xcompressed=(Xv1)v1T=σ1u1v1T
Each entry in the column vector Xv1 is a single number telling how far along v1 a point projects. Multiplying that column of distances by the row vector v1T turns each projection back into a 2D point sitting on the line through v1, which is the first term of the SVD:
Xcompressed=(Xv1)v1TPoints on the line through v1=(σ1u1)v1TSince Xv1=σ1u1 from X=UΣVT=σ1u1v1TRank-1 approximation of X
Keeping the top k principal components in higher dimensions simply keeps the first k rank-1 pieces of the SVD:
Xcompressed=σ1u1v1T+σ2u2v2T+⋯+σkukvkT
Key concepts
Every PCA problem starts by centering the data at (0,0): subtract (Avg x1,Avg x2) from each point before stacking the N points as the rows of X (for (1,2),(3,4),(5,4),(7,6) with average (4,4), the first row of X is [−3−2]).
From the centered matrix X, the covariance matrixC=N1XTX records the horizontal variance Avg of x12 and vertical variance Avg of x22 on the diagonal, and the tilt Avg of x1x2 off the diagonal (in C=[5332], the positive +3 means the cloud tilts up and right; a negative off-diagonal entry means it tilts down and right). For any unit vector u, the variance along u is the quadratic form uTCu.
The principal components and extreme variances are the perpendicular unit eigenvectors and eigenvalues of the symmetric matrix C. The largest eigenvalue λ1 is the maximum variance (along Principal Component 1, v1), and the smallest eigenvalue λ2 is the minimum variance (along v2). Because the total variance is λ1+λ2=trace(C), Principal Component 1 captures the fraction trace(C)λ1 of the total variance (for C=[5332],λ1≈6.85 out of trace(C)=7, or 98%). To project and reconstruct, Xv1 gives the column of N signed 1D distances along the line, and Xcompressed=(Xv1)v1T puts those points back into the original space along the line through v1.
When not to form C=N1XTX: if the centered matrix X is already given in SVD form X=UΣVT, skip multiplying out XTX. Read the principal directions vi directly from the columns of V, compute their variances from λi=Nσi2 (for N=10 and σ1=15,λ1=10152=22.5), and write the rank-k compressed matrix as σ1u1v1T+⋯+σkukvkT.
5
Practice
1
Given N=4 data points in 2D: (1,5),(2,3),(4,3), and (5,1). Center the data at (0,0) to form the centered data matrix X, compute the covariance matrix C=41XTX, and explain what the off-diagonal entry tells you about the cloud.
Be careful not to stack the uncentered points directly into X. Skipping the centering step gives 41XTX=[11.57711] with a false positive off-diagonal entry +7 just because all four points sit in the first quadrant.Remember to divide by N=4, or you will get [10−8−88].
Find the average (Avg x1,Avg x2) of the four points first. What must you do to each coordinate before stacking the rows into X?
Find the center of the four points and subtract it from each coordinate to form X:
(Be careful not to stack the uncentered points directly into X. Skipping the centering step gives 41XTX=[11.57711] with a false positive off-diagonal entry +7 just because all four points sit in the first quadrant.)
Multiply 41XTX (and remember to divide by N=4, or you will get [10−8−88]):
The negative off-diagonal covariance (−2) means x1 and x2 move in opposite directions, so the cloud tilts down and to the right.
2
A centered 2D dataset has covariance matrix C=[5228]. Find the variance of the projections along the unit vector u=[0.60.8], then find the maximum and minimum possible variances across all unit directions and the percentage of total variance captured by Principal Component 1.
Variance along a unit vector u is the quadratic form uTCu; which properties of C give the extreme values of uTCu and the total variance across all directions?
Evaluate the quadratic form uTCu for the variance along u:
Use trace(C)=5+8=13 and det(C)=(5)(8)−(2)(2)=36 to find the eigenvalues of C (do not read the diagonal entries 8 and 5 as the maximum and minimum variances; that ignores the off-diagonal tilt 2, and 8.84 is already larger than 8):
Divide the top eigenvalue λ1=9 (not the vertical variance 8, which gives 138≈61.5%) by the total variance trace(C)=5+8=13:
trace(C)λ1=139≈69.2%
3
The centered data matrix X=−11−5511−2−10102 has covariance matrix C=41XTX=[73363652] with eigenvalues λ1=100 and λ2=25. Find the perpendicular unit eigenvectors v1 and v2, compute the 1D projections Xv1 along Principal Component 1, and reconstruct the compressed 2D points Xcompressed=(Xv1)v1T.
Be sure to normalize v1 to length 1 before projecting. Using the unnormalized vector [43] scales Xv1 by 5 to −50−505050 and scales Xcompressed by 25 to −200−200200200−150−150150150.
Solve (C−100I)v1=0 and remember to scale v1 to length 1 before computing Xv1.
Solve (C−100I)v1=0 and (C−25I)v2=0, and divide by 42+32=5 so both eigenvectors have unit length:
(Be sure to normalize v1 to length 1 before projecting. Using the unnormalized vector [43] scales Xv1 by 5 to −50−505050 and scales Xcompressed by 25 to −200−200200200−150−150150150.)
Multiply X by v1 for the 1D projections, then multiply by v1T for the reconstructed 2D points on the line through v1:
A centered data matrix X for N=10 points in 3D has the Singular Value Decomposition X=UΣVT with singular values σ1=15,σ2=4,σ3=3 and V=323231−32313231−3232. Without computing XTX, find the three principal directions v1,v2,v3 and their variances λ1,λ2,λ3, the percentage of total variance captured by keeping the top two principal components, and the SVD expression for the rank-2 compressed data matrix.
Do not forget to divide by N=10, which would give 225,16,9.
How do the columns of V and the singular values σi of X relate to the eigenvectors and eigenvalues of C=N1XTX?
Read the three principal directions directly from the columns of V:
Square each singular value and divide by N=10 to find the variances (do not forget to square σi, which would give 15+4+315+4≈86.4%, and do not forget to divide by N=10, which would give 225,16,9):
λ1=10152=22.5,λ2=1042=1.6,λ3=1032=0.9
Sum the three eigenvalues for the total variance and find the share captured by the top two components: