PCA: Eigenvalue Decomposition of the Covariance Matrix

Recommended resources

The freely available resources this lesson will direct you to.

Introduction

Welcome to our second lesson on unsupervised learning. In our previous discussion, we explored K-means clustering, a method for partitioning data into distinct groups based on geometric proximity. We now shift our focus from partitioning data to re-representing it in a more compact and informative way. This leads us to the topic of dimensionality reduction, a crucial task in machine learning for visualization, noise reduction, and improving computational efficiency.

This lesson introduces Principal Component Analysis (PCA), arguably the most fundamental and widely used technique for linear dimensionality reduction. Our goal is to derive PCA from first principles, showing that it is equivalent to performing an eigenvalue decomposition of the data's covariance matrix. By the end of this lesson, you will understand the theoretical objective of PCA—to find a new basis that maximizes variance and minimizes redundancy—and how this objective is solved using core concepts from linear algebra.

The Objective of PCA: Maximizing Variance and Minimizing Redundancy

Imagine you have a high-dimensional dataset. It's likely that some of the features are correlated, meaning they contain redundant information. For example, in a dataset of house features, square_footage and number_of_bedrooms are likely to be strongly correlated. The core idea of PCA is to find a new set of coordinate axes, called principal components, to represent the data. These new axes should be chosen to meet two primary criteria:

Maximize Variance: Each successive component should capture the maximum possible remaining variance in the data. The directions with the largest variance are assumed to contain the most "signal" or information.
Ensure Orthogonality: The new axes must be orthogonal to each other. In statistical terms, this means the resulting features will be uncorrelated, thereby eliminating redundancy.

To formalize this, let's consider the statistics of the data. For a dataset $X$ , we can describe the spread and relationships between its features using the covariance matrix.

The diagonal entries of the covariance matrix represent the variance of each individual feature.
The off-diagonal entries represent the covariance between pairs of features, quantifying their linear relationship.

With this in mind, the goal of PCA can be restated: we want to find a new basis (an orthogonal transformation) for the data such that the covariance matrix of the transformed data is diagonal. A diagonal covariance matrix has zero on all its off-diagonal entries, which perfectly captures our requirement that the new features be uncorrelated. The diagonal entries themselves will represent the variance along each of the new axes. Our goal is to find a transformation that not only diagonalizes the covariance matrix but also orders the new axes such that the first axis has the largest variance, the second has the second-largest, and so on.

The following document provides an excellent, detailed intuition for this objective.

A TUTORIAL ON PRINCIPAL COMPONENT ANALYSIS

This tutorial builds the conceptual framework for PCA by discussing what it means to "best express" data. It focuses on the ideas of signal (variance) and redundancy (covariance).

Please read Section 4, "Variance and the Goal". Pay close attention to how it connects the high-level goals of reducing noise and redundancy to the statistical concepts of variance and covariance, culminating in the goal of diagonalizing the covariance matrix.

The Linear Algebra of PCA: Eigen-Decomposition

Having established our goal, we now turn to the mechanics of achieving it. This is where your background in linear algebra becomes central. The problem of finding an orthogonal transformation that diagonalizes a symmetric matrix is precisely the problem solved by eigenvalue decomposition.

Let's begin with a quick refresher on the key concepts. An eigenvector of a square matrix is a non-zero vector that, when multiplied by the matrix, is simply scaled by a constant factor, the eigenvalue. It changes in length, but not in direction. For symmetric matrices, such as a covariance matrix, the eigenvectors are orthogonal.

The MIT OpenCourseWare video below provides a rigorous and clear review of eigenvectors, eigenvalues, and the covariance matrix. It will be an effective way to refresh these concepts before we apply them to the PCA derivation.

17: Principal Components Analysis_ - Intro to Neural Computation

This lecture from "Intro to Neural Computation" covers the essential linear algebra needed for PCA.

First, watch the segment on eigenvectors and eigenvalues to solidify your geometric and algebraic understanding of these concepts. Next, review the section on summarizing symmetric matrix decomposition, which introduces the form A = \Phi \Lambda \Phi^T. This is the exact decomposition we will use. Finally, watch the explanation of covariance in higher dimensions, which formally introduces the covariance matrix and its role in describing the shape of high-dimensional data distributions.

Deriving PCA

Now we are equipped to derive the solution to PCA. Let our data be represented by an $m \times n$ matrix $X$ , where $m$ is the number of features and $n$ is the number of samples. We assume the data has been mean-centered (i.e., the mean of each feature has been subtracted from it).

The covariance matrix of the data is given by $C_{X} = \frac{1}{n - 1} X X^{T}$ . Note that $C_{X}$ is an $m \times m$ symmetric matrix.
We seek an orthogonal transformation matrix $P$ that re-expresses the data as $Y = P X$ . The rows of $P$ will be our new basis vectors—the principal components.
The covariance matrix of the transformed data, $C_{Y}$ , is:
$C_{Y} = \frac{1}{n - 1} Y Y^{T} = \frac{1}{n - 1} (P X) (P X)^{T} = \frac{1}{n - 1} P X X^{T} P^{T} = P (\frac{1}{n - 1} X X^{T}) P^{T} = P C_{X} P^{T}$
Our goal is to choose $P$ such that $C_{Y}$ is a diagonal matrix, let's call it $D$ . The problem is to find an orthogonal matrix $P$ that satisfies $D = P C_{X} P^{T}$ .
This is the standard form of orthogonal diagonalization. A fundamental theorem of linear algebra states that any symmetric matrix (like $C_{X}$ ) can be decomposed as:
$C_{X} = E D E^{T}$
Here, $E$ is an orthogonal matrix whose columns are the orthonormal eigenvectors of $C_{X}$ , and $D$ is a diagonal matrix whose entries are the corresponding eigenvalues.

This diagram shows the eigenvalue decomposition of a matrix A. For a symmetric matrix, the matrix of eigenvectors Q is orthogonal, meaning Q⁻¹ = Qᵀ. In our derivation, Cₓ plays the role of A, and E plays the role of Q.

To solve our problem, we simply choose our transformation matrix $P$ to be the transpose of the eigenvector matrix, $P = E^{T}$ . Let's substitute this into our expression for $C_{Y}$ : $C_{Y} = P C_{X} P^{T} = E^{T} (E D E^{T}) (E^{T})^{T} = E^{T} (E D E^{T}) E$ Since $E$ is an orthogonal matrix, $E^{T} E = I$ (the identity matrix). $C_{Y} = (E^{T} E) D (E^{T} E) = I D I = D$

We have successfully diagonalized the covariance matrix. The transformed data $Y$ has a diagonal covariance matrix $D$ , which means its new features are uncorrelated.

The profound result is this:

The principal components (the rows of our transformation matrix $P = E^{T}$ ) are the eigenvectors of the data's covariance matrix $C_{X}$ .
The variances of the data projected onto these new principal components are the eigenvalues of $C_{X}$ .

The following resource provides a concise, formal walkthrough of this exact derivation.

A TUTORIAL ON PRINCIPAL COMPONENT ANALYSIS

This section directly derives the algebraic solution for PCA.

Read Section 5, "Solving PCA: Eigenvectors of Covariance". This short section lays out the mathematical steps exactly as we have discussed, proving that the eigenvectors of the covariance matrix form the principal components. You may also find it helpful to look at Appendix A, theorems 3 and 4, for proofs regarding the diagonalization of symmetric matrices.

An Alternative View: Maximizing Projected Variance

Another way to formulate the PCA problem is as a direct optimization problem: find the unit vector $u$ that maximizes the variance of the data when projected onto it. This variance is given by $u^{T} C_{X} u$ . Using the method of Lagrange multipliers to maximize this quantity subject to the constraint that $u$ is a unit vector ( $u^{T} u = 1$ ), we arrive at the same conclusion:

$C_{X} u = λ u$

This is the eigenvalue equation. It shows that the direction of maximum variance must be an eigenvector of the covariance matrix. The maximum variance itself is the corresponding eigenvalue. This alternative derivation reinforces the conclusion from a different theoretical starting point, which can deepen the understanding.

This video provides a great visual explanation of this optimization perspective.

Principal Component Analysis (PCA)

This video from "Visually Explained" presents PCA as an optimization problem.

Watch the segment from the beginning to see how the goal of preserving information leads to an optimization problem, which is then solved using Lagrange multipliers to reveal the underlying eigenvalue equation.

Conclusion

In this lesson, we established the theoretical foundations of Principal Component Analysis. We moved from the high-level intuition of finding a more informative data representation to a rigorous mathematical derivation.

Here are the key takeaways:

PCA's Objective: To find a new, orthogonal basis for the data that maximizes variance and eliminates correlation between the new features.
The Covariance Matrix: This matrix is central to PCA. Its diagonal elements are the variances of the original features, and its off-diagonal elements are the covariances. PCA's goal is to find a transformation that makes this matrix diagonal.
The Derivation: By framing the problem as the orthogonal diagonalization of the covariance matrix $C_{X}$ , we proved that the solution is found through its eigenvalue decomposition.
The Solution: The principal components are the eigenvectors of the data covariance matrix. The corresponding eigenvalues represent the variance captured by each principal component.

You now understand why PCA is synonymous with the eigen-decomposition of the covariance matrix. In our next lesson, we will build upon this by exploring how to interpret the results of PCA. Specifically, we will focus on the eigenvalues, or "explained variance," to make practical decisions about how many principal components to retain for effective dimensionality reduction.