PCA and SVD: A Fundamental Relationship

1. From Covariance to SVD: Two Paths to the Same Goal

As we concluded last time, the principal components are the axes of a new coordinate system aligned with the data's spread. Mathematically, these axes are the eigenvectors of the data's covariance matrix.

Let's formalize this. Assume we have a data matrix $X$ with $n$ samples (rows) and $d$ features (columns).

1. First, we mean-center the data by subtracting the mean of each column from all entries in that column. Let's call this centered matrix $B$.
2. The sample covariance matrix $S$ is then given by $S=\frac{1}{n-1}{B}^{T}B$. This is a $d\times d$ symmetric matrix.
3. The principal components are the eigenvectors of this covariance matrix $S$, ordered by the size of their corresponding eigenvalues. The eigenvalues themselves represent the variance of the data along each principal component direction.

This gives us one clear method: form the covariance matrix and find its eigenvectors. However, there is a more direct and numerically stable way using SVD. Let's see how these two paths converge.

2. The SVD Connection

The main insight for today's lesson is that we can bypass the explicit calculation of the covariance matrix. The SVD of the centered data matrix itself gives us the principal components.

The following video provides an excellent walkthrough of the entire PCA process, culminating in the connection to SVD.

Let's break down the beautiful mathematical connection shown in the video.

Let the SVD of our mean-centered data matrix $B$ be:
$B=U\Sigma V^T$

Now, let's construct the covariance matrix $S$ using this decomposition.
$S=\frac{1}{n-1}{B}^{T}B=\frac{1}{n-1}(U\Sigma V^T{)}^T(U\Sigma V^T)$

Using the property $(ABC{)}^T=C^T{B}^T{A}^T$, we get:
$S=\frac{1}{n-1}(V{\Sigma }^T{U}^T)(U\Sigma V^T)$

Since the left singular vectors in $U$ form an orthonormal set of columns, we know that $U^{T}U=I$ (the identity matrix). This simplifies the expression dramatically:
$S=\frac{1}{n-1}V({\Sigma }^T\Sigma )V^T$

This final equation is incredibly revealing. It is the eigendecomposition of the covariance matrix $S$.

• The columns of $V$ are the eigenvectors of $S$.
• The diagonal matrix $\frac{1}{n-1}{\Sigma }^T\Sigma$ contains the eigenvalues of $S$.

Since the principal components are, by definition, the eigenvectors of the covariance matrix, we have found them:

The principal components of the data are the right singular vectors (the columns of $V$) of the mean-centered data matrix $B$.

To solidify this, let's turn to a more detailed textual explanation of this relationship.

3. The PCA Algorithm via SVD

This direct relationship gives us a robust and numerically stable algorithm for performing PCA, which is the standard approach in modern software packages. Given your background in computer science, it's worth noting that computing the SVD of $B$ is generally preferred over forming $B^{T}B$ and finding its eigenvectors. Forming the product $B^{T}B$ can lead to a loss of precision, an issue that specialized SVD algorithms are designed to avoid.

Here is the complete algorithm:

1. Organize Data: Start with your dataset as an $n\times d$ matrix $X$, where $n$ is the number of samples and $d$ is the number of features.
2. Center the Data: For each feature column, calculate its mean and subtract it from the column to produce the centered matrix $B$.
3. Compute SVD: Calculate the SVD of the centered matrix: $B=U\Sigma V^T$.
4. Identify Components and Scores:
   • The principal components (the directions of variance) are the columns of the matrix $V$. The first column of $V$ is the first principal component, the second column is the second, and so on.
   • The principal component scores (the coordinates of the data in the new basis) are given by the matrix product $BV$. A little algebra shows this is simply $U\Sigma$. Each column of $U\Sigma$ gives the scores for the corresponding principal component.

The singular values in $\Sigma$ tell you the importance of each component. The variance explained by the $i$-th component is $\frac{{\sigma }_i^2}{n-1}$. By looking at these values, you can decide how many components to keep for dimensionality reduction.

Conclusion

In this lesson, we've solidified the connection between the abstract goal of PCA and its practical implementation via SVD. This is a cornerstone concept in data analysis, where the geometric interpretation of finding directions of maximum variance maps perfectly onto the algebraic decomposition of a matrix.

Key Takeaways:

• Principal Component Analysis can be performed in two equivalent ways: by finding the eigenvectors of the covariance matrix, or by computing the SVD of the centered data matrix.
• The principal components are precisely the right singular vectors ($V$) of the mean-centered data matrix.
• The eigenvalues of the covariance matrix are directly proportional to the squares of the singular values (${\lambda }_i={\sigma }_i^2/(n-1)$), quantifying the variance along each principal component.
• The projected data points onto the new principal component axes, known as scores, are given by the columns of the matrix $U\Sigma$.
• Using SVD is the standard, numerically preferred method for computing PCA.

Preview of the Next Module:

This lesson concludes our module on "Applications in Data Analysis". We've seen how SVD is a golden thread connecting least squares, matrix approximation, and now PCA.

Our next module, "Tensor Products for Composite Systems," will take us in a new direction, one that is absolutely essential for your goal of studying quantum mechanics. We will learn how to combine vector spaces to describe systems made of multiple parts—for example, how to describe the state of two particles (or two qubits) when we know the state of each one individually. This will introduce concepts like the Kronecker product and the crucial quantum idea of entanglement.