Relationship between SVD and Eigen-decomposition

Eigen-decomposition is typically applied to square matrices to find directions (eigenvectors) that remain unchanged (up to scaling) under the transformation represented by the matrix. For a matrix $A$, the eigenvalue equation is $Ax = \lambda x$. If $A$ is symmetric, its eigen-decomposition takes the form $A = V \Lambda V^T$, where $V$ contains the orthogonal eigenvectors and $\Lambda$ is a diagonal matrix of eigenvalues.

Singular Value Decomposition (SVD), $A = U\Sigma V^T$, provides a related but more general way to decompose any matrix $A$, whether square or rectangular. The connection between SVD and eigen-decomposition becomes clear when we consider the matrices $A^T A$ and $A A^T$. These matrices are always square and symmetric (or more precisely, positive semi-definite), which means their eigen-decomposition is well-behaved.

Let's see how the components of SVD ($U$, $\Sigma$, $V$) relate to the eigen-decomposition of these specific matrices.

Connection via $A^T A$

Consider the matrix $A^T A$. Let's substitute the SVD of $A$ into this expression: $A = U \Sigma V^T$ $A^T = (U \Sigma V^T)^T = V \Sigma^T U^T$

Now, multiply $A^T$ by $A$: $A^T A = (V \Sigma^T U^T) (U \Sigma V^T)$

Since $U$ is an orthogonal matrix, $U^T U = I$ (the identity matrix). The expression simplifies: $A^T A = V \Sigma^T (U^T U) \Sigma V^T$ $A^T A = V (\Sigma^T \Sigma) V^T$

Look closely at this result: $A^T A = V (\Sigma^T \Sigma) V^T$. This is exactly the form of an eigen-decomposition for the symmetric matrix $A^T A$.

• The columns of $V$ are the eigenvectors of $A^T A$.
• The matrix $\Sigma^T \Sigma$ is a diagonal matrix. Its diagonal entries are the eigenvalues of $A^T A$.

What are the diagonal entries of $\Sigma^T \Sigma$? If $\Sigma$ has the singular values $\sigma_1, \sigma_2, ..., \sigma_r$ on its diagonal (where $r$ is the rank of $A$), then $\Sigma^T \Sigma$ is an $n \times n$ diagonal matrix with $\sigma_1^2, \sigma_2^2, ..., \sigma_r^2$ followed by zeros on its diagonal.

So, the right singular vectors of $A$ (the columns of $V$) are the eigenvectors of $A^T A$. The squared singular values of $A$ ($\sigma_i^2$) are the eigenvalues of $A^T A$.

Connection via $A A^T$

Now let's perform a similar analysis for the matrix $A A^T$: $A A^T = (U \Sigma V^T) (V \Sigma^T U^T)$

Since $V$ is also an orthogonal matrix, $V^T V = I$. The expression simplifies: $A A^T = U \Sigma (V^T V) \Sigma^T U^T$ $A A^T = U (\Sigma \Sigma^T) U^T$

Again, this result $A A^T = U (\Sigma \Sigma^T) U^T$ is the eigen-decomposition for the symmetric matrix $A A^T$.

• The columns of $U$ are the eigenvectors of $A A^T$.
• The matrix $\Sigma \Sigma^T$ is a diagonal matrix. Its diagonal entries are the eigenvalues of $A A^T$.

The diagonal entries of $\Sigma \Sigma^T$ are also the squared singular values $\sigma_1^2, \sigma_2^2, ..., \sigma_r^2$, followed by zeros (this time it's an $m \times m$ matrix).

So, the left singular vectors of $A$ (the columns of $U$) are the eigenvectors of $A A^T$. The squared singular values of $A$ ($\sigma_i^2$) are also the eigenvalues of $A A^T$.

Summary of the Relationship

SVD Component ($A = U\Sigma V^T$)	Relationship to Eigen-decomposition
Singular Values ($\sigma_i$)	Square roots of non-zero eigenvalues of $A^T A$ (and $A A^T$)
Right Singular Vectors ($V$)	Eigenvectors of $A^T A$
Left Singular Vectors ($U$)	Eigenvectors of $A A^T$

This relationship is significant for several reasons:

1. Generality: It shows how SVD extends the ideas of eigen-decomposition (finding special directions and scaling factors) from square matrices to any rectangular matrix via the symmetric matrices $A^T A$ and $A A^T$.
2. Computation: While you could theoretically compute SVD by finding the eigen-decompositions of $A^T A$ and $A A^T$, numerical methods directly computing SVD are generally more stable and preferred in practice.
3. Interpretation in ML: In many data analysis scenarios, $A$ represents centered data points as rows. The matrix $A^T A$ is closely related to the covariance matrix of the features. The eigen-decomposition of the covariance matrix is the core of Principal Component Analysis (PCA). Therefore, the right singular vectors ($V$) and singular values ($\sigma_i$) from the SVD of the data matrix $A$ are directly linked to the principal components and the variance captured by them. Specifically, the right singular vectors $V$ give the principal directions, and the squared singular values $\sigma_i^2$ (scaled appropriately) give the variance along those directions.

Practical Demonstration with NumPy

Let's verify this relationship using Python's NumPy library. We'll create a sample matrix $A$, compute its SVD, and then compute the eigen-decompositions of $A^T A$ and $A A^T$ to see if the components match as expected.

import numpy as np

# Set print options for better readability
np.set_printoptions(suppress=True, precision=4)

# Create a sample non-square matrix A
A = np.array([[1, 2, 3],
              [4, 5, 6]]) # A is 2x3

print("Matrix A:\n", A)

# 1. Compute SVD of A
# U will be 2x2, S will contain 2 singular values, Vh (V.T) will be 3x3
U, s, Vh = np.linalg.svd(A)
V = Vh.T # Transpose Vh to get V
Sigma_squared = s**2

print("\nSVD Results:")
print("U (Left Singular Vectors):\n", U)
print("Singular Values (s):", s)
print("Sigma^2 (Squared Singular Values):", Sigma_squared)
print("V (Right Singular Vectors):\n", V)

# 2. Compute Eigen-decomposition of A.T @ A (A^T A)
ATA = A.T @ A # ATA is 3x3
print("\nMatrix A^T A:\n", ATA)

# Use eigh for symmetric matrices (returns sorted eigenvalues/vectors)
eigenvalues_ATA, eigenvectors_ATA = np.linalg.eigh(ATA)

# Eigenvalues from eigh are sorted smallest to largest, reverse them
eigenvalues_ATA = eigenvalues_ATA[::-1]
eigenvectors_ATA = eigenvectors_ATA[:, ::-1]

print("\nEigen-decomposition of A^T A:")
print("Eigenvalues (should match Sigma^2):", eigenvalues_ATA)
print("Eigenvectors (should match columns of V):\n", eigenvectors_ATA)

# 3. Compute Eigen-decomposition of A @ A.T (A A^T)
AAT = A @ A.T # AAT is 2x2
print("\nMatrix A A^T:\n", AAT)

eigenvalues_AAT, eigenvectors_AAT = np.linalg.eigh(AAT)

# Reverse sort order for consistency
eigenvalues_AAT = eigenvalues_AAT[::-1]
eigenvectors_AAT = eigenvectors_AAT[:, ::-1]

print("\nEigen-decomposition of A A^T:")
print("Eigenvalues (should match Sigma^2):", eigenvalues_AAT)
print("Eigenvectors (should match columns of U):\n", eigenvectors_AAT)

# Verification Checks (allowing for small numerical differences)
print("\nVerification:")
# Check eigenvalues
print("Sigma^2 matches eigenvalues of A^T A (approx):", np.allclose(Sigma_squared, eigenvalues_ATA[:len(s)]))
print("Sigma^2 matches eigenvalues of A A^T (approx):", np.allclose(Sigma_squared, eigenvalues_AAT[:len(s)]))

# Check eigenvectors (Note: Eigenvectors are unique only up to sign)
# Check if columns of V match eigenvectors_ATA (or their negative)
print("Columns of V match eigenvectors of A^T A (approx):",
      np.allclose(np.abs(V[:, :len(s)]), np.abs(eigenvectors_ATA[:, :len(s)])))

# Check if columns of U match eigenvectors_AAT (or their negative)
print("Columns of U match eigenvectors of A A^T (approx):",
      np.allclose(np.abs(U), np.abs(eigenvectors_AAT)))

Running this code demonstrates the connection:

• The non-zero eigenvalues of both $A^T A$ and $A A^T$ are equal to the squares of the singular values ($\sigma_i^2$). Note that $A^T A$ might have more eigenvalues than $A A^T$ (or vice versa) if $A$ is rectangular, but the non-zero ones will match $\sigma_i^2$.
• The eigenvectors of $A^T A$ correspond to the columns of $V$ (right singular vectors).
• The eigenvectors of $A A^T$ correspond to the columns of $U$ (left singular vectors).

Remember that eigenvectors (and singular vectors) are unique only up to a sign ($\pm 1$). So, when comparing vectors like $V$ and the eigenvectors of $A^T A$, you might find that some corresponding columns are negatives of each other. This is perfectly normal and np.allclose comparing absolute values handles this.

This deep connection between SVD and eigen-decomposition solidifies SVD as a fundamental tool. It uses the well-understood properties of symmetric matrix eigen-decomposition to provide a powerful decomposition for any matrix, with direct applications in understanding data structure, dimensionality reduction, and more.