Articles / Linear Algebra · Part 20
Singular Value Decomposition (SVD)
Learn Singular Value Decomposition (SVD), calculate singular values and vectors, and explore its applications in compression, machine learning, and dimensionality reduction.
In previous articles, we studied LU and QR decomposition, where matrices were broken into simpler components to solve systems of equations and perform calculations efficiently.
Singular Value Decomposition (SVD) takes matrix factorization further. It allows us to represent any matrix as a product of three matrices, revealing important information about its structure, dimensions, and the transformations it performs.
SVD is particularly useful in:
- Machine Learning
- Data Compression
- Recommendation Systems
- Image Processing
- Dimensionality Reduction
- Noise Reduction
It is one of the most important matrix factorization techniques in modern data science.
2. What Is Singular Value Decomposition?
Singular Value Decomposition expresses a matrix (A) as:
\[
\boxed{A=U\Sigma V^T}
\]
where:
- U: Contains orthonormal left singular vectors.
- Σ (Sigma): Contains singular values along its diagonal.
- V: Contains orthonormal right singular vectors.
For an \(m\times n\) matrix \(A\), the full SVD is:
\[
A=U\Sigma V^T
\]
with:
\[
U\in\mathbb R^{m\times m}
\]
\[
\Sigma\in\mathbb R^{m\times n}
\]
\[
V\in\mathbb R^{n\times n}
\]
The columns of (U) and (V) are orthonormal.
The singular values are non-negative and are usually arranged in descending order:
\[
\sigma_1\geq\sigma_2\geq\cdots\geq0
\]
3. Understanding the Three Matrices
Matrix U — Left Singular Vectors
The columns of (U) represent orthonormal directions in the output space.
These vectors describe the directions in which the transformed data lies.
Matrix Σ — Singular Values
The singular values describe how strongly the matrix stretches or compresses different directions.
A large singular value represents a direction with significant influence, while a small singular value represents a direction with relatively little influence.
\[
\Sigma=
\begin{bmatrix}
\sigma_1&0&0\\
0&\sigma_2&0\\
0&0&\sigma_3
\end{bmatrix}
\]
For rectangular matrices, Sigma may also be rectangular.
Matrix V — Right Singular Vectors
The columns of (V) represent orthonormal directions in the input space.
They identify the directions that the transformation acts upon before stretching, compressing, or rotating them.
4. How SVD Is Calculated
A common method for understanding and calculating SVD begins with the matrix:
\[
A^TA
\]
The matrix \(A^TA\) is symmetric and positive semidefinite. Its eigenvalues are non-negative.
The relationship between eigenvalues and singular values is:
\[
\boxed{\sigma_i=\sqrt{\lambda_i}}
\]
where \(\lambda_i\) are the eigenvalues of \(A^TA\).
The eigenvectors of \(A^TA\) form the columns of \(V\).
Similarly, the eigenvectors of \(AA^T\) form the columns of \(U\).
The general process is:
- Calculate \(A^TA\).
- Find its eigenvalues.
- Calculate the singular values by taking the square roots of the eigenvalues.
- Find the corresponding eigenvectors to construct \(V\).
- Calculate the left singular vectors to construct \(U\).
- Assemble \(U\), \(\Sigma\), and \(V^T\).
5. Step-by-Step SVD Example
Consider the matrix:
\[
A=
\begin{bmatrix}
1&0\\
0&1\\
1&1
\end{bmatrix}
\]
This is a \(3\times2\) matrix.
We want to find its singular value decomposition:
\[
A=U\Sigma V^T
\]
Step 1: Calculate \(A^TA\)
First, transpose the matrix:
\[
A^T=
\begin{bmatrix}
1&0&1\\
0&1&1
\end{bmatrix}
\]
Multiply:
\[
A^TA=
\begin{bmatrix}
1&0&1\\
0&1&1
\end{bmatrix}
\begin{bmatrix}
1&0\\
0&1\\
1&1
\end{bmatrix}
\]
\[
A^TA=
\begin{bmatrix}
2&1\\
1&2
\end{bmatrix}
\]
Step 2: Find the Eigenvalues
We solve:
\[
\det(A^TA-\lambda I)=0
\]
\[
\begin{vmatrix}
2-\lambda&1\\
1&2-\lambda
\end{vmatrix}=0
\]
\[
(2-\lambda)^2-1=0
\]
\[
\lambda^2-4\lambda+3=0
\]
Factor:
\[
(\lambda-3)(\lambda-1)=0
\]
Therefore:
\[
\lambda_1=3,\qquad\lambda_2=1
\]
Step 3: Calculate the Singular Values
Singular values are the square roots of the eigenvalues:
\[
\sigma_1=\sqrt3,\qquad\sigma_2=1
\]
Therefore:
\[
\Sigma=
\begin{bmatrix}
\sqrt3&0\\
0&1
\end{bmatrix}
\]
Step 4: Find the Right Singular Vectors
The right singular vectors are the normalized eigenvectors of \(A^TA\).
For \(\lambda_1=3\), the eigenvector is:
\[
\mathbf{v}_1=
\frac1{\sqrt2}
\begin{bmatrix}
1\\1
\end{bmatrix}
\]
For \(\lambda_2=1\), the eigenvector is:
\[
\mathbf{v}_2=
\frac1{\sqrt2}
\begin{bmatrix}
1\\-1
\end{bmatrix}
\]
Therefore:
\[
V=
\begin{bmatrix}
\frac1{\sqrt2}&\frac1{\sqrt2}\\
\frac1{\sqrt2}&-\frac1{\sqrt2}
\end{bmatrix}
\]
Step 5: Find the Left Singular Vectors
We calculate:
\[
\mathbf{u}_i=\frac{A\mathbf{v}_i}{\sigma_i}
\]
For the first singular vector:
\[
\mathbf{u}_1=
\frac{A\mathbf{v}_1}{\sqrt3}
\]
\[
\mathbf{u}_1=
\frac1{\sqrt6}
\begin{bmatrix}
1\\1\\2
\end{bmatrix}
\]
For the second singular vector:
\[
\mathbf{u}_2=A\mathbf{v}_2
\]
\[
\mathbf{u}_2=
\frac{1}{\sqrt2}
\begin{bmatrix}
1\\
-1\\
0
\end{bmatrix}
\]
Therefore, the reduced (U) matrix is:
\[
U=
\begin{bmatrix}
\frac{1}{\sqrt6}&\frac{1}{\sqrt2}\\
\frac{1}{\sqrt6}&-\frac{1}{\sqrt2}\\
\frac{2}{\sqrt6}&0
\end{bmatrix}
\]
Step 6: Assemble the SVD
Our final decomposition is:
\[
\boxed{A=U\Sigma V^T}
\]
where:
\[
U=
\begin{bmatrix}
\frac{1}{\sqrt6}&\frac{1}{\sqrt2}\\
\frac{1}{\sqrt6}&-\frac{1}{\sqrt2}\\
\frac{2}{\sqrt6}&0
\end{bmatrix}
\]
\[
\Sigma=
\begin{bmatrix}
\sqrt3&0\\
0&1
\end{bmatrix}
\]
and:
\[
V^T=
\begin{bmatrix}
\frac{1}{\sqrt2}&\frac{1}{\sqrt2}\\
\frac{1}{\sqrt2}&-\frac{1}{\sqrt2}
\end{bmatrix}
\]
Multiplying these three matrices reconstructs the original matrix (A).
6. Geometric Interpretation of SVD
SVD can be understood as a sequence of three transformations.
For a vector \(\mathbf{x}\), the transformation:
\[
A\mathbf{x}=U\Sigma V^T\mathbf{x}
\]
can be interpreted as:
- \(V^T\): Rotates or changes the input direction into a new coordinate system.
- \(\Sigma\): Stretches or compresses along specific directions.
- \(U\): Rotates or maps the result into the output space.
This decomposition makes the behavior of a complicated transformation easier to understand.
7. Applications of SVD
Dimensionality Reduction
SVD identifies the most important directions in data. By retaining only the largest singular values, we can represent data using fewer dimensions while preserving much of its important information.
Image Compression
Images can be represented as matrices. SVD allows us to approximate an image using fewer components, reducing storage requirements while retaining visual information.
Recommendation Systems
SVD can uncover hidden patterns in user-item data, such as movie ratings, allowing systems to predict what a user might enjoy.
Noise Reduction
Small singular values often represent less significant information or noise. Removing selected components can help produce cleaner data.
Natural Language Processing
SVD is used in methods such as Latent Semantic Analysis to identify relationships between words and documents.
8. Low-Rank Approximation
One of the most powerful applications of SVD is low-rank approximation.
Instead of using every singular value, we retain only the largest (k) singular values.
\[
A\approx U_k\Sigma_kV_k^T
\]
This produces a smaller representation of the original matrix.
The larger singular values generally capture more of the matrix’s structure, while smaller singular values contribute less.
This is useful when we want to:
- Compress data.
- Reduce dimensions.
- Remove noise.
- Simplify large matrices.
- Reduce computational requirements.
Singular Value Decomposition is a powerful matrix factorization technique that represents any matrix as:
\[
A=U\Sigma V^T
\]
It separates a transformation into orthogonal directions and scaling values, allowing us to understand the structure of data and matrices.
Its applications in compression, machine learning, recommendation systems, and dimensionality reduction make it one of the most important tools in modern Linear Algebra.
Key takeaway: SVD reveals the most important directions and patterns hidden inside a matrix.
Quick quiz
5 questionsOriginally published at farhanpaal.com — https://farhanpaal.com/articles/singular-value-decomposition-svd/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com