6.1 Theory and properties of SVD

Singular Value Decomposition (SVD) is a powerful matrix factorization technique that breaks down any matrix into three components. It's like a Swiss Army knife for linear algebra, revealing crucial information about a matrix's structure and behavior.

SVD has wide-ranging applications, from data compression to machine learning. By understanding its properties and interpretations, we gain insights into matrix transformations, principal directions, and the relative importance of different components in linear systems.

Singular Value Decomposition

Definition and Basic Properties

Top images from around the web for Definition and Basic Properties

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Basic Properties

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

• 

  Singular value decomposition - Wikipedia View original

  Is this image relevant?

1 of 3

• SVD decomposes matrix A into A = UΣV^T where U and V are orthogonal matrices and Σ contains singular values
• For m × n matrix A, U (m × m) contains left singular vectors, Σ (m × n) holds singular values, V^T (n × n) contains right singular vectors
• Singular values in Σ arranged in descending order along diagonal (non-negative real numbers)
• Number of non-zero singular values equals rank of matrix A
• SVD exists for any real or complex matrix (regardless of dimensions or rank)
• SVD uniqueness determined by singular vector signs and singular value ordering
• Computes pseudoinverse of matrix (useful for underdetermined or overdetermined linear systems)

Applications and Interpretations

• Singular values represent scaling factors of linear transformation along principal axes
• Largest singular value indicates direction of maximum stretching or compression
• Left singular vectors (U columns) represent principal directions in domain space
• Right singular vectors (V columns) represent principal directions in range space
• Product of singular value and corresponding left/right singular vectors contributes to overall transformation
• Ratio of successive singular values shows relative importance of transformation components
• Singular vectors for zero singular values span null space (right) and left null space (left) of matrix A

Singular Values and Vectors

Geometric Interpretation

• Singular values scale linear transformation along principal axes (stretching or compressing)
• Largest singular value corresponds to maximum stretching/compression direction
• Left singular vectors (U columns) represent principal directions in input space
• Right singular vectors (V columns) represent principal directions in output space
• Singular value product with left/right singular vectors contributes to transformation (scaling factor)
• Successive singular value ratios indicate relative importance of transformation components
• Zero singular value vectors span null spaces (right for null space, left for left null space)

Mathematical Properties

• Non-negative real numbers arranged in descending order on Σ diagonal
• Number of non-zero singular values equals matrix rank
• Orthonormal columns in U and V matrices
• Relationship between singular vectors: Av_i = σ_i u_i (σ_i is i-th singular value)
• Singular values are square roots of A^T A (or AA^T) eigenvalues
• Left singular vectors (U) are eigenvectors of AA^T
• Right singular vectors (V) are eigenvectors of A^T A

SVD Derivation

Eigendecomposition Approach

• Derive SVD using eigendecomposition of A^T A and AA^T
• A^T A and AA^T eigenvalues are squares of A's singular values
• A^T A eigenvectors form V columns (right singular vectors)
• AA^T eigenvectors form U columns (left singular vectors)
• Singular vector relationship: Av_i = σ_i u_i (σ_i is i-th singular value)
• For symmetric matrices, SVD equals eigendecomposition (singular values are absolute eigenvalues)
• Derivation process involves solving characteristic equations for A^T A and AA^T, normalizing resulting eigenvectors

Algorithmic Computation

• Iterative methods (QR algorithm) compute SVD numerically
• Householder transformations reduce matrix to bidiagonal form
• Divide-and-conquer algorithms efficiently handle large matrices
• Randomized SVD algorithms approximate decomposition for massive datasets
• Jacobi rotations iteratively diagonalize matrix for small to medium-sized problems
• Lanczos methods compute partial SVD for sparse matrices
• Power iteration calculates dominant singular values/vectors

SVD vs Other Decompositions

Comparison with Eigendecomposition

• SVD generalizes eigendecomposition to non-square matrices
• SVD provides more stable decomposition for numerical computations
• For symmetric positive definite matrices, SVD equals eigendecomposition (singular values = eigenvalues, singular vectors = eigenvectors)
• SVD applies to any matrix, while eigendecomposition requires square matrices
• SVD reveals both left and right singular vectors, eigendecomposition focuses on one set of vectors

Relation to QR Decomposition

• QR decomposition used as step in computing SVD through iterative methods (QR algorithm)
• SVD viewed as two-sided orthogonalization, QR provides one-sided orthogonalization
• SVD offers more comprehensive factorization than QR (reveals column and row space information)
• SVD computes Moore-Penrose pseudoinverse (generalizes matrix inversion to non-square and singular matrices)
• QR decomposition primarily used for solving linear systems and least squares problems
• SVD more computationally expensive than QR, but provides more detailed matrix analysis