PCA: Maximizing Variance with Lagrange Multipliers

Welcome to Module 11! In the previous modules, we explored unsupervised learning through the lens of clustering, where our goal was to discover hidden groups within our data. We now shift our focus to another fundamental task in unsupervised learning: dimensionality reduction.

High-dimensional data is everywhere, from images with millions of pixels to financial models with thousands of features. Working with such data presents challenges in computation, visualization, and interpretation—often called the "curse of dimensionality." Principal Component Analysis (PCA) is one of the most widely used and powerful techniques for addressing this problem.

Today's lesson addresses the first learning outcome for this module: to derive Principal Component Analysis (PCA) from first principles by maximizing variance using Lagrange Multipliers. We will build the entire method from the ground up, starting with a simple intuitive goal and using calculus and linear algebra to arrive at a beautiful and profound result. This approach, centered on a formal derivation, is tailored to your interest in the mathematical underpinnings of data science algorithms.

1. The Core Idea: Maximizing Variance

Imagine you have a cloud of data points in a high-dimensional space. If you were forced to represent this data using only one dimension (i.e., projecting it onto a single line), which line would you choose? Intuitively, you'd want to pick the line that spreads the projected data out as much as possible, thereby preserving the most information about the original data's structure. In statistical terms, "spreading out" means maximizing the variance of the projected data.

This is the central idea of PCA. The first principal component is the direction in space along which the data varies the most. The second principal component is the direction that captures the most remaining variance, with the added condition that it must be orthogonal (perpendicular) to the first. This process continues, with each subsequent component being orthogonal to all previous ones.

The following video provides an excellent high-level introduction to this concept.

Principal Component Analysis (PCA)

The video 'Principal Component Analysis (PCA)' by Visually Explained offers a great conceptual start. It uses a real-world example to explain why we need PCA and what it aims to achieve.

Watch the first minute of the video (0:00 - 1:05) to get a feel for the problem PCA solves and the goal of creating new, ranked factors (principal components) that preserve information.

2. Formulating the Problem Mathematically

Let's translate this idea into mathematics. We have a dataset of $n$ data points $x_{1}, x_{2}, \dots, x_{n}$ , where each $x_{i} \in R^{p}$ . For simplicity, we'll assume the data has been centered, meaning the mean of the data points is the zero vector.

Our goal is to find a direction, represented by a unit vector $u \in R^{p}$ (so that $u^{T} u = 1$ ), onto which we can project our data.

The projection of a single data point $x_{i}$ onto the line defined by $u$ is a scalar value given by the dot product $u^{T} x_{i}$ . The variance of these projected points is:

Var (projections) = \frac{1}{n} i = 1 \sum n (u^{T} x_{i} - mean of projections)^{2}

Since the original data is centered, the mean of the projections is also zero ( $\frac{1}{n} \sum u^{T} x_{i} = u^{T} (\frac{1}{n} \sum x_{i}) = 0$ ). So, the variance simplifies to:

Var (projections) = \frac{1}{n} i = 1 \sum n (u^{T} x_{i})^{2}

This expression can be rewritten in a more compact matrix form, which is crucial for the derivation. The following video walks through this process.

Principal Component Analysis (The Math) : Data Science Concepts

The video 'Principal Component Analysis (The Math)' by ritvikmath provides a rigorous step-by-step derivation. This first segment sets up the problem and rewrites the variance in terms of the covariance matrix, a key step for our optimization.

Watch the segment from 2:02 to 8:09. Follow the derivation closely as it moves from the geometric idea of maximizing spread to the algebraic formulation for the variance of the projections. The key result you should understand is that the variance can be written as \mathbf{u}^T \mathbf{S} \mathbf{u}, where \mathbf{S} is the sample covariance matrix of the data.

As derived in the video, the variance of the projected data is neatly expressed as:

Var (projections) = u^{T} Su

where $S = \frac{1}{n} \sum_{i = 1}^{n} x_{i} x_{i}^{T}$ is the sample covariance matrix of our centered data.

Our problem is now clearly defined:

Maximize: $u^{T} Su$
Subject to the constraint: $u^{T} u = 1$ (i.e., $u$ is a unit vector)

3. The Derivation: Lagrange Multipliers to the Rescue

This is a classic constrained optimization problem, perfectly suited for the method of Lagrange multipliers. As you may recall from your math background, this method converts a constrained problem into an unconstrained one by introducing a new variable, the Lagrange multiplier $λ$ .

We form the Lagrangian function $L$ :

L (u, λ) = u^{T} Su - λ (u^{T} u - 1)

To find the maximum, we take the gradient of $L$ with respect to $u$ and set it to zero. Using matrix calculus identities ( $\frac{\partial}{\partial x} (x^{T} Ax) = 2 Ax$ for symmetric $A$ and $\frac{\partial}{\partial x} (x^{T} x) = 2 x$ ), we get:

\frac{\partial L}{\partial u} = 2 Su - 2 λ u = 0

This simplifies to a familiar and powerful equation:

Su = λ u

This is the eigenvalue equation! This remarkable result tells us that the optimal direction $u$ must be an eigenvector of the covariance matrix $S$ .

But which eigenvector? Let's go back to our objective function, the variance. If we pre-multiply our result by $u^{T}$ :

u^{T} Su = u^{T} (λ u) = λ (u^{T} u)

Since our constraint is $u^{T} u = 1$ , this simplifies to:

u^{T} Su = λ

The variance we wanted to maximize is simply the eigenvalue $λ$ . Therefore, to maximize the variance, we must choose the eigenvector $u$ that corresponds to the largest eigenvalue $λ$ .

The following segment of the video walks through exactly this derivation.

Principal Component Analysis (The Math) : Data Science Concepts

Let's continue with the same video to see the Lagrange multiplier method in action.

Watch the segment from 8:09 to 12:15. This part is the core of today's lesson. It formulates the Lagrangian, takes the derivative, and arrives at the conclusion that the principal components are the eigenvectors of the covariance matrix, ranked by their eigenvalues.

To solidify this crucial derivation, please study the following formal proof. It mirrors the steps we've just discussed and serves as an excellent reference.

PCA: A formal description with proofs

This resource from a Multivariate Statistics course provides a concise, formal proof of the PCA derivation using Lagrange multipliers. It's a great way to review and consolidate the material from the video.

Read the text up to and including the 'Proof' section for Proposition 4.1. Focus on the derivation for the first component (j=1), which directly corresponds to what we've just covered.

4. Subsequent Principal Components

We have now found the first principal component, $v_{1}$ , which is the eigenvector of $S$ with the largest eigenvalue $λ_{1}$ .

How do we find the second principal component, $v_{2}$ ? We follow the same logic: we want to find the direction that maximizes the variance, but with a new constraint that it must be orthogonal to $v_{1}$ .

Maximize: $u^{T} Su$
Subject to: $u^{T} u = 1$ and $u^{T} v_{1} = 0$

The inductive proof in the resource LINK shows that solving this new problem leads to the eigenvector of $S$ corresponding to the second-largest eigenvalue. This pattern continues for all subsequent components. The $k$ -th principal component is the eigenvector of the covariance matrix corresponding to the $k$ -th largest eigenvalue.

Conclusion

In this lesson, we derived Principal Component Analysis from first principles. We started with the intuitive goal of finding the direction of maximum variance in a dataset and used the method of Lagrange multipliers to solve this constrained optimization problem.

Key Takeaways:

PCA is a dimensionality reduction technique that finds a new set of orthogonal axes, called principal components, that align with the directions of maximum variance in the data.
The problem of finding the first principal component can be formulated as maximizing the variance of the projected data ( $u^{T} Su$ ) subject to the constraint that the projection axis is a unit vector ( $u^{T} u = 1$ ).
Solving this using Lagrange multipliers leads directly to the eigenvalue equation $Su = λ u$ .
This proves that the principal components are the eigenvectors of the data's covariance matrix $S$ . The amount of variance captured by each component is given by its corresponding eigenvalue $λ$ .
To capture the most variance, the principal components are chosen by ranking the eigenvectors according to their corresponding eigenvalues in descending order.

Preview of the Next Lesson

We have just completed the core mathematical derivation of PCA. In the next lesson, we will build on this foundation to explain the geometric interpretation of PCA as a rotation of the coordinate system. We will also see how the solution we found today is deeply connected to the eigendecomposition of the covariance matrix, solidifying the link between the abstract goal of maximizing variance and the concrete machinery of linear algebra.