Singular Value Decomposition (SVD)

The Singular Value Decomposition (SVD) represents the pinnacle of matrix factorizations. While the eigendecomposition is restricted to square matrices (and further limited by diagonalizability), the SVD is universal. Every linear operator $A:{\mathbb{K}}^n\to {\mathbb{K}}^m$ (where $\mathbb{K}=\mathbb{R}$ or $\mathbb{C}$) possesses an SVD, providing profound insights into the geometry and numerical stability of the transformation.

1. The SVD Theorem

Let $A\in {\mathbb{C}}^{m\times n}$ be a matrix of rank $r$. There exists a factorization of the form:

$A=U\Sigma V^{\ast }$

where:

• $U\in {\mathbb{C}}^{m\times m}$ is a unitary matrix ($U^{\ast }U=I_m$). Its columns are called the left singular vectors.
• $V\in {\mathbb{C}}^{n\times n}$ is a unitary matrix ($V^{\ast }V=I_n$). Its columns are the right singular vectors.
• $\Sigma \in {\mathbb{R}}^{m\times n}$ is a rectangular diagonal matrix with non-negative real entries ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_{\min (m,n)}\ge 0$ on the diagonal. These are the singular values.

In the real case ($A\in {\mathbb{R}}^{m\times n}$), $U$ and $V$ are orthogonal matrices, and the decomposition is $A=U\Sigma V^T$.

2. Derivation and Link to Eigendecomposition

The SVD is intimately connected to the spectral properties of the hermitian matrices $A^{\ast }A$ and $A{A}^{\ast }$.

1. Right Singular Vectors ($V$): Consider $A^{\ast }A\in {\mathbb{C}}^{n\times n}$. Since $A^{\ast }A$ is positive semi-definite and Hermitian, its eigenvalues are real and non-negative. Let these be ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$. The right singular vectors $v_i$ are the orthonormal eigenvectors of $A^{\ast }A$. $(A^{\ast }A)v_i={\lambda }_i{v}_i$
2. Singular Values ($\Sigma$): The singular values are the square roots of these eigenvalues: ${\sigma }_i=\sqrt{{\lambda }_i}$.
3. Left Singular Vectors ($U$): These are the orthonormal eigenvectors of $A{A}^{\ast }\in {\mathbb{C}}^{m\times m}$. For ${\sigma }_i>0$, they are uniquely determined by: $u_i=\frac{1}{{\sigma }_i}A{v}_i$

3. Geometric Intuition

Geometrically, the SVD asserts that any linear transformation can be decomposed into a rotation in the domain, a scaling along principal axes, and a rotation in the codomain.

Imagine a unit sphere $S$ in ${\mathbb{R}}^n$. Under the transformation $A$, this sphere is mapped to a hyper-ellipsoid in ${\mathbb{R}}^m$.

• The singular values ${\sigma }_i$ are the lengths of the semi-axes of the ellipsoid.
• The left singular vectors $u_i$ define the directions of these semi-axes in the codomain.
• The right singular vectors $v_i$ define the orthonormal basis in the domain that maps to these semi-axes.

4. Properties of Singular Values

• Non-negativity: ${\sigma }_i\ge 0$ for all $i$.
• Ordering: Conventionally, ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$.
• Rank: The number of non-zero singular values is exactly the rank $r$ of the matrix $A$.
• Norms:
  • Spectral Norm: $\Vert A{\Vert }_2={\sigma }_1$.
  • Frobenius Norm: $\Vert A{\Vert }_F=\sqrt{{\sigma }_1^2+\cdots +{\sigma }_r^2}$.
• Condition Number: For an invertible square matrix, $\kappa (A)={\sigma }_1/{\sigma }_n$.

5. The Moore-Penrose Pseudoinverse

For any matrix $A$, we define the pseudoinverse $A^{†}$ via the SVD:

$A^{†}=V{\Sigma }^{†}{U}^{\ast }$

where ${\Sigma }^{†}$ is obtained by taking the reciprocal of each non-zero element on the diagonal of ${\Sigma }^T$.

Applications in Linear Systems: For an overdetermined system $Ax=b$, the least-squares solution that minimizes $\Vert Ax-b{\Vert }_2$ is given by $\hat{x}=A^{†}b$. If multiple solutions exist (underdetermined), $A^{†}b$ provides the solution with the minimum Euclidean norm.

6. Low-Rank Approximation

The Eckart–Young–Mirsky Theorem provides the theoretical foundation for data compression. It states that the best rank-$k$ approximation of $A$ (where $k<r$) in the Frobenius norm is given by:

$A_k={\sum }_{i=1}^k{\sigma }_i{u}_i{v}_i^{\ast }$

The approximation error is $\Vert A-A_k{\Vert }_F=\sqrt{{\sum }_{i=k+1}^r{\sigma }_i^2}$. This property is utilized in Principal Component Analysis (PCA) to reduce dimensionality while preserving maximum variance.

7. Polar Decomposition

The SVD enables the Polar Decomposition, analogous to the polar form of complex numbers ($z=r{e}^{i\theta }$). Any square matrix $A$ can be written as:

$A=QS$

where $Q$ is unitary (representing rotation/reflection) and $S$ is a positive semi-definite Hermitian matrix (representing scaling/stretching).

• Using SVD: $A=(U{V}^{\ast })\cdot (V\Sigma V^{\ast })$.
• Here $Q=U{V}^{\ast }$ and $S=V\Sigma V^{\ast }$.

8. Python Implementation: Rank-k Approximation

The following script performs a rank-$k$ approximation on a randomly generated matrix and quantifies the relative error.

import numpy as np

def rank_k_approximation(A, k):
    # Perform SVD
    U, S, Vh = np.linalg.svd(A, full_matrices=False)
    
    # Construct Sigma_k
    Sk = np.diag(S[:k])
    
    # Reconstruct rank-k matrix
    Ak = U[:, :k] @ Sk @ Vh[:k, :]
    
    # Calculate Frobenius norm error
    full_norm = np.linalg.norm(A, 'fro')
    error_norm = np.linalg.norm(A - Ak, 'fro')
    
    return Ak, error_norm / full_norm

# Example usage
m, n = 100, 50
A = np.random.randn(m, n)
k = 10

Ak, rel_error = rank_k_approximation(A, k)
print(f"Original Rank: {np.linalg.matrix_rank(A)}")
print(f"Target Rank: {k}")
print(f"Relative Frobenius Error: {rel_error:.4f}")

9. Applications in Physics and Engineering

• Image Compression: By treating an image as a matrix and keeping only the top $k$ singular values, we store $k(m+n+1)$ values instead of $mn$.
• PCA (Principal Component Analysis): In statistics, SVD is applied to the covariance matrix to find the directions of maximum variance.
• Signal Processing: SVD is used to separate signal from noise, as noise typically corresponds to small singular values.