Singular Value Decomposition (SVD)

Subtopic: Decompositions

The SVD factors any matrix — even rectangular ones — into rotation, scaling, and rotation: A=U*Σ*VT.

It reveals the fundamental structure of linear maps and enables dimensionality reduction, pseudoinverses, and matrix approximation. SVD is arguably the most important matrix factorization in applied mathematics.

Introduction

Eigendecomposition only works for square matrices, and only some of those. SVD works for every matrix. It decomposes a linear map into: rotate input space → stretch along coordinate axes → rotate to output space.

This universal factorization makes SVD the Swiss army knife of linear algebra.

Definition

Any m×n matrix A can be factored as A=U*Σ*VT, where:

• U is m×m orthogonal (columns are left singular vectors)

• Σ is m×n diagonal with nonnegative entries (singular values (σ_1)≥(σ_2)≥⋯≥0)

• V is n×n orthogonal (columns are right singular vectors)

Geometric Interpretation

Multiplying by A transforms vectors in three steps:

• VT rotates or reflects in the input space

• Σ stretches along coordinate axes (by (σ_i))

• U rotates or reflects into the output space

The singular values (σ_i) are the stretching factors along principal axes. The unit sphere maps to an ellipsoid; the (σ_i) are the semi-axis lengths.

Relation to Eigenvalues

The singular values (σ_i) are the square roots of the eigenvalues of AT*A (or A*AT):

(σ_i)=√(,(λ_i)*(AT*A)).

• Columns of V are eigenvectors of AT*A

• Columns of U are eigenvectors of A*AT

For symmetric positive definite matrices, singular values equal eigenvalues.

Worked Example

Find the SVD of:

A=([3,0],[0,2],[0,0])

This is already "SVD-ready." The singular values are (σ_1)=3, (σ_2)=2.

U=([1,0,0],[0,1,0],[0,0,1]),Σ=([3,0],[0,2],[0,0]),V=([1,0],[0,1])

Verify: U*Σ*VT=A

The Truncated SVD

Keeping only the k largest singular values gives the best rank-k approximation:

(A_k)=(∑_i=1^k)((σ_i))*(u_i)*(v_i)T

This minimizes ‖A-(A_k)‖ among all rank-k matrices (in both Frobenius and spectral norms).

Crucial for dimensionality reduction: keep the most important directions, discard noise.

Key Properties

• rank(A)= number of nonzero singular values

• ∥A∥=(σ_1) (spectral norm = largest singular value)

• ∥A∥=√(,(∑_^)((σ_i)2)) (Frobenius norm)

• Condition number =(σ_max())/(σ_min())

• Pseudoinverse: A+=V*Σ+*UT, where Σ+ inverts the nonzero (σ_i)

Applications

In image compression, SVD keeps the largest singular values, dramatically reducing storage with small quality loss.

In recommendation systems, SVD reveals latent factors connecting users and items (e.g., the Netflix Prize).

In PCA, the principal components are the right singular vectors; singular values determine component importance.

In least squares, the pseudoinverse (via SVD) solves A*x≈b when A is not invertible.

Summary

The SVD factors A=U*Σ*VT into orthogonal matrices and a diagonal matrix of singular values. It works for any matrix and reveals rank, norms, and condition number. Truncated SVD gives optimal low-rank approximations. Singular values are the square roots of the eigenvalues of AT*A. Applications span dimensionality reduction, compression, recommendation, and solving ill-conditioned systems.