SVD and Eigendecomposition of AᵀA

Welcome to the fourth lesson in our foundational module. In our previous sessions, we've been building up the calculus machinery needed for machine learning. Last time, we focused on the practical task of differentiating common matrix expressions, culminating in the gradient of the least squares objective function.

Today, we take a short but crucial detour back into the world of linear algebra to cover the Singular Value Decomposition (SVD). You mentioned that SVD was a topic you were less comfortable with, and this lesson is designed to address that directly. SVD is a cornerstone of numerical linear algebra and has profound applications in machine learning, from Principal Component Analysis (PCA) to recommendation systems. Our goal is to understand what SVD is and, most importantly, to establish its direct relationship with the eigendecomposition of a matrix, a concept you're already familiar with.

1. The Geometric Intuition Behind SVD

Before diving into the algebra, let's build a strong geometric picture of what SVD does. At its heart, any matrix $A$ represents a linear transformation; it takes vectors from an input space and maps them to an output space. SVD tells us that any such transformation, no matter how complex it seems, can be broken down into three fundamental geometric operations:

A rotation (or reflection).
A scaling along the new axes.
Another rotation (or reflection).

The following image provides a beautiful illustration of this process.

This diagram shows how applying a matrix M to a set of unit vectors (top left) is equivalent to performing a sequence of three simpler transformations: a rotation (V*), a scaling (Σ), and a final rotation (U). The SVD of M is the algebraic representation of this geometric decomposition.

The formula at the bottom of the image, $M = U Σ V^{*}$ , is the Singular Value Decomposition. Let's define the components for a real-valued matrix $A$ of size $m \times n$ :

A = U Σ V^{T}

$U$ is an $m \times m$ orthogonal matrix. Its columns, called the left singular vectors, form an orthonormal basis for the output space ( $R^{m}$ ). Geometrically, this matrix performs the final rotation.
$V$ is an $n \times n$ orthogonal matrix. Its columns, called the right singular vectors, form an orthonormal basis for the input space ( $R^{n}$ ). Its transpose, $V^{T}$ , performs the initial rotation.
$Σ$ is an $m \times n$ rectangular diagonal matrix. The non-negative values on its diagonal, $σ_{1}, σ_{2}, \dots$ , are the singular values of $A$ , conventionally ordered from largest to smallest. This matrix performs the stretching or squashing along the axes.

The power of SVD is that it exists for any matrix $A$ , regardless of whether it's square, symmetric, or invertible. It provides a stable and insightful way to understand the action of any linear map.

2. The Bridge: Connecting SVD to Eigendecomposition

This geometric picture is helpful, but how do we actually find the matrices $U$ , $Σ$ , and $V$ ? The answer, surprisingly, lies in the eigendecomposition of two related symmetric matrices: $A^{T} A$ and $A A^{T}$ .

Since you are comfortable with eigendecomposition, we can use it as a bridge to construct the SVD. Let's start with the definition $A = U Σ V^{T}$ and see what happens when we compute $A^{T} A$ :

A^{T} A = (U Σ V^{T})^{T} (U Σ V^{T})

Using the transpose rule $(X Y Z)^{T} = Z^{T} Y^{T} X^{T}$ , we get:

A^{T} A = (V Σ^{T} U^{T}) (U Σ V^{T})

Because $U$ is an orthogonal matrix, its columns are orthonormal, meaning $U^{T} U = I$ (the identity matrix). This simplifies our expression significantly:

A^{T} A = V Σ^{T} U^{T} U Σ V^{T} = V (Σ^{T} Σ) V^{T}

Now, look closely at this final form: $A^{T} A = V (Σ^{T} Σ) V^{T}$ . This is precisely the eigendecomposition of the symmetric matrix $A^{T} A$ !

$V$ is the matrix of eigenvectors.
$(Σ^{T} Σ)$ is the diagonal matrix of eigenvalues.

This gives us a concrete procedure for finding $V$ and $Σ$ . The following short video provides a very clear walkthrough of this exact derivation.

Singular Values vs. Eigenvalues : Data Science Basics

This video from the channel ritvikmath clearly explains the connection between singular values and eigenvalues. It walks through the same algebraic steps we just took.

Please watch the entire video (the full video). Pay close attention to the derivation from M transpose M, which shows how the right singular vectors and singular values of a matrix M are the eigenvectors and square roots of eigenvalues of M transpose M, respectively.

3. Formalizing the Relationship

The video provided a great overview. Let's now formalize this crucial relationship by studying a more detailed document.

27 Positive (Semi)Definite Matrices, Gram Matrices, SVD

This document provides a formal proof of the connection between SVD and the eigendecompositions of A^T A and AA^T.

Please read the section titled "Properties of the SVD and Connection to AAT and ATA". Focus on the subsection "Relationship with ATA". It repeats the derivation we just did, solidifying the following key points.

Let's summarize the profound connection we've established:

The right singular vectors of $A$ (the columns of $V$ ) are the eigenvectors of the symmetric matrix $A^{T} A$ .
The squares of the singular values of $A$ (the $σ_{i}^{2}$ ) are the eigenvalues of $A^{T} A$ . This is why singular values are always non-negative.
Similarly, though we didn't derive it in detail, the left singular vectors of $A$ (the columns of $U$ ) are the eigenvectors of the symmetric matrix $A A^{T}$ .

This relationship provides a robust method for computing the SVD of any matrix $A$ .

4. A Worked Example

Theory is essential, but seeing it in action solidifies understanding. Since you prefer active learning, let's walk through a concrete example. The following resource provides a step-by-step calculation.

Chapter 7 The Singular Value Decomposition (SVD)

This excerpt from a classic linear algebra textbook by Gilbert Strang shows a complete SVD calculation for a 2x2 matrix.

Please read the section titled "An Example of the SVD". Follow the steps for the matrix A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}. Try to work through the calculations yourself as you read: Compute A^T A. Find its eigenvalues (\lambda_i) and corresponding normalized eigenvectors (v_i). The singular values are \sigma_i = \sqrt{\lambda_i}. This gives you \Sigma. The eigenvectors form the columns of V. The left singular vectors u_i are found using the relationship u_i = \frac{1}{\sigma_i} A v_i. These form the columns of U. Finally, check that the assembled U \Sigma V^T indeed gives back A.

Working through this example connects all the pieces: the algebraic definition, the connection to eigendecomposition, and the practical computation of all three SVD components.

Conclusion

In this lesson, we demystified the Singular Value Decomposition. We saw that it represents any linear transformation as a sequence of rotation, scaling, and a final rotation. More importantly, we established the fundamental link between SVD and a topic you're already familiar with: eigendecomposition.

Here are the key takeaways:

Any $m \times n$ matrix $A$ can be factored as $A = U Σ V^{T}$ .
The right singular vectors (columns of $V$ ) are the eigenvectors of $A^{T} A$ .
The singular values ( $σ_{i}$ ) are the square roots of the eigenvalues of $A^{T} A$ .
The left singular vectors (columns of $U$ ) are the eigenvectors of $A A^{T}$ .

We have now added another powerful tool to our mathematical arsenal. SVD is not just an abstract decomposition; it is the engine behind many machine learning algorithms, particularly in dimensionality reduction, which we will explore in a later module.

In our next lesson, we will pivot from linear algebra back to optimisation. We'll introduce the concept of convexity, a property of functions that is absolutely central to our ability to find optimal solutions for machine learning models efficiently and reliably.

Recommended resources

1. The Geometric Intuition Behind SVD

2. The Bridge: Connecting SVD to Eigendecomposition

3. Formalizing the Relationship

4. A Worked Example

Conclusion