Singular Value Decomposition (SVD)

• is a generalization of eigen-decomposition, decomposing rectangular matrices
• related to singular values
• is like a "data-driven" Fast Fourier Transform (FFT)

if 𝐴𝑥 = 𝜆𝑥 & ||𝑥|| = 1, then:

• ||𝐴𝑥|| = ||𝜆𝑥||
• ||𝐴𝑥|| = |𝜆| ||𝑥||
  
• ||𝐴𝑥|| = |𝜆|
  

SVD - Definition (Real and/or Complex Matrix)

The SVD of an 𝑚✕𝑛 real and/or complex matrix 𝐴 with rank 𝑟 is:

• 𝐴 = 𝑈𝛴𝑉*

where:

• 𝑈 - 𝑚✕𝑚 real or complex unitary matrix
• 𝛴 - 𝑚✕𝑛 rectangular matrix with diagonal entries of the first 𝑟 singular values of 𝐴 (𝜎₁ ≥ 𝜎₂ ≥ ... ≥ 𝜎_𝑟)
• 𝑉 - 𝑛✕𝑛 real or complex unitary matrix (𝑉* - complex conjugate of 𝑉)
  

SVD - Definition (Real Matrix)

If 𝐴 is real, 𝑈 and 𝑉*=𝑉^𝑇 are real orthogonal matrices (where 𝑉^𝑇 is the transpose)

• 𝐴 = 𝑈𝛴𝑉^𝑇

where:

• 𝑈 - orthogonal 𝑚✕𝑚 unitary matrix. normalized eigenvectors of the symmetric matrix 𝐴𝐴^𝑇 (𝑖.𝑒. 𝑈^𝑇𝑈=𝐼) columns of 𝑈 are called the left singular vectors of 𝐴
• 𝑉 - orthogonal 𝑛✕𝑛 unitary matrix. normalized eigenvectors of the symmetric matrix 𝐴^𝑇𝐴 (𝑖.𝑒. 𝑉^𝑇𝑉=𝐼) columns of 𝑉 are called the right singular vectors of 𝐴
• 𝛴 - diagonal matrix of singular values
• 𝛴 = 𝐷^(1/2) where 𝐷 is the diagonal matrix of the eigenvalues of matrix 𝐴𝐴^𝑇 and 𝐴^𝑇𝐴

derivation:

The Invertible Matrix Theorem

let 𝐴 be 𝑛✕𝑛 matrix. then the following statements are equivalent to the statement that 𝐴 is an invertible matrix:

• (𝐶𝑜𝑙𝐴)^⟂ = {0}
• (N𝑢𝑙𝑙𝐴)^⟂ = ℝ^𝑛
• 𝑅𝑜𝑤𝐴 = ℝ^𝑛
• 𝐴 has 𝑛 non-zero singular values

SVD - Reduced SVD & Pseudo Inverse (Moore-Penrose Inverse)

𝑈_𝑟𝐷𝑉_𝑟^𝑇 is called reduced SVD

pseudoinverse (Moore-Penrose Inverse) of 𝐴:

• 𝐴^† = 𝑉_𝑟𝐷^-1𝑈_𝑟^𝑇

application to least-squares solution

given the equation 𝐴𝑥 = 𝑏, use pseudoinverse of 𝐴

• 𝑥̂ = 𝐴^†𝑏
• 𝑥̂ = 𝑉_𝑟𝐷^-1𝑈_𝑟^𝑇𝑏

then from SVD:

• 𝐴𝑥̂ = 𝑈_𝑟𝐷𝑉_𝑟^𝑇𝑉_𝑟𝐷^-1𝑈_𝑟^𝑇𝑏
• 𝐴𝑥̂ = 𝑈_𝑟𝑈_𝑟^𝑇𝑏
  

SVD - Intuition (As Linear Transformations)

SVD - Subpages

• SVD - Image Compression (Python)

Resources

• Brunton and Kutz: Video Lectures