Matrix Decomposition with SVD

1. The Core Idea: Decomposing Any Matrix

Singular Value Decomposition states that any $m\times n$ matrix $A$ can be factored into three other matrices:

Where:

• $U$ is an $m\times m$ orthogonal matrix whose columns are the left singular vectors.
• $\Sigma$ (Sigma) is an $m\times n$ diagonal matrix. The diagonal entries, ${\sigma }_1,{\sigma }_2,...$, are the singular values of A. They are always non-negative and are arranged in descending order (${\sigma }_1\ge {\sigma }_2\ge ...\ge 0$).
• $V^T$ is the transpose of an $n\times n$ orthogonal matrix $V$, whose columns are the right singular vectors.

The diagram below gives a great visual representation of how these matrices fit together.

Conceptually, you can think of SVD as breaking down the original transformation $A$ into three separate, simpler operations:

1. A rotation or reflection ($V^T$).
2. A scaling along the axes ($\Sigma$).
3. Another rotation or reflection ($U$).

The crucial connection to our last lesson is this: the singular values (${\sigma }_i$) in $\Sigma$ are the square roots of the eigenvalues of the square matrix $A^{T}A$. The columns of $V$ are the corresponding eigenvectors of $A^{T}A$.

2. How to Calculate SVD: A Step-by-Step Process

Let's outline the manual process for finding the SVD of a matrix $A$. This process directly builds upon your knowledge of finding eigenvalues and eigenvectors.

1. Compute $A^{T}A$. This will always result in a square, symmetric matrix.
2. Find the eigenvalues of $A^{T}A$. Solve the characteristic equation $\det (A^{T}A-\lambda I)=0$.
3. Construct $\Sigma$. The singular values are the square roots of the eigenvalues you just found: ${\sigma }_i=\sqrt{{\lambda }_i}$. Place these values, in descending order, on the main diagonal of a matrix $\Sigma$ with the same dimensions as $A$.
4. Find $V$. The columns of $V$ are the normalized eigenvectors of $A^{T}A$ corresponding to the eigenvalues.
5. Find $U$. The columns of $U$ can be calculated using the formula ${\mathbf{u}}_i=\frac{1}{{\sigma }_i}A{\mathbf{v}}_i$, where ${\mathbf{v}}_i$ are the columns of $V$.
6. Assemble the decomposition. Combine the matrices to get $A=U\Sigma V^T$. Remember to take the transpose of $V$.

This process might seem complex, so let's watch a video where it's done step-by-step for a 2x2 matrix.

3. SVD for a Non-Square Matrix

The real power of SVD is that it works for rectangular matrices. The procedure is the same, but the dimensions of $\Sigma$ and $U$ will be different. Let's walk through an excellent text-based example.

4. SVD in Python: A Practical First Look

While performing SVD by hand is essential for understanding the mechanics, in practice, you'll always use a library like NumPy. As you prepare for your GATE exam and future work in data science, being able to apply these concepts in code is crucial.

The numpy.linalg module has a convenient function, svd(), that does all the heavy lifting for us. Let's get an introduction to how it works and what its outputs mean.

Here is a simple code snippet demonstrating the core idea from the video. You can try running this yourself in a Python environment.

import numpy as np

# Define a matrix A
A = np.array([[3, 2, 2],
              [2, 3, -2]])

print("Original Matrix A:")
print(A)

# Perform SVD
# The svd() function returns U, a 1D array of singular values (s), and V_transpose (Vt)
U, s, Vt = np.linalg.svd(A)

print("\nMatrix U:")
print(U)
print("\nSingular values (s):")
print(s)
print("\nMatrix V_transpose (Vt):")
print(Vt)

# To reconstruct A, we need to convert the 1D array 's' into a diagonal matrix 'Sigma'
# with the correct dimensions (same as A's).
Sigma = np.zeros(A.shape)
Sigma[:min(A.shape), :min(A.shape)] = np.diag(s)

print("\nDiagonal Matrix Sigma:")
print(Sigma)

# Reconstruct the original matrix
A_reconstructed = U @ Sigma @ Vt

print("\nReconstructed Matrix A:")
print(np.round(A_reconstructed, decimals=2)) # Rounding to handle floating point inaccuracies

# Verify the reconstruction is close to the original
assert np.allclose(A, A_reconstructed)
print("\nVerification successful: U @ Sigma @ Vt is indeed A!")

This ability to decompose a matrix and then reconstruct it (or an approximation of it) is fundamental to many advanced machine learning techniques.

Conclusion

Congratulations on completing this lesson on Singular Value Decomposition! It's a challenging but deeply rewarding topic. You've bridged the gap from the theoretical world of eigenvalues for square matrices to a practical tool that can be applied to any matrix.

Key Takeaways:

• Any matrix $A$ can be decomposed into $A=U\Sigma V^T$, where $U$ and $V$ are orthogonal matrices and $\Sigma$ is a diagonal matrix.
• The singular values in $\Sigma$ are the square roots of the eigenvalues of $A^{T}A$, and they represent the "magnitudes" of the principal components of the matrix.
• The columns of $V$ are the eigenvectors of $A^{T}A$.
• SVD can be computed manually by finding eigenvalues/eigenvectors, but in practice, we use library functions like numpy.linalg.svd.
• A major application of SVD is creating low-rank approximations of a matrix for tasks like data compression.

In our next lesson, we will fully focus on the practical side. We will use NumPy to compute determinants, inverses, eigenvalues, and SVD of matrices. This will solidify your coding skills and ensure you can efficiently apply all the linear algebra concepts we've covered in this module.