Computing SVD

Linear Algebra for Machine Learning · Axiom Academy

Step-by-Step Algorithm for Finding Singular Value Decomposition While modern software uses sophisticated numerical algorithms (like the Golub-Kahan algorithm), we can compute SVD conceptually through eigendecomposition of A T A. Start by computing the Gram matrix A T A, which is an n × n symmetric matrix. Why this works: The matrix A T A is symmetric (A T A = (A T A) T ), which means it has real eigenvalues and orthogonal eigenvectors. Step 2: Find Eigenvalues and Eigenvectors of A T A Perform eigendecomposition of A T A: Let λ₁, λ₂, ..., λₙ be the eigenvalues and v₁, v₂, ..., vₙ be the corresponding orthonormal eigenvectors. Step 3: Compute Singular Values The singular values are the square roots of the eigenvalues of A T A: After computing σᵢ, arrange them (and the corresponding eigenvectors vᵢ) in decreasing order: Form V T by transposing the matrix of eigenvectors: Form Σ as an m × n diagonal matrix: U can be computed from the relationship A = UΣV T . For the first r non-zero singular values: where uᵢ is the i-th column of U and σᵢ is the i-th singular value. Find eigenvalues λᵢ and eigenvectors vᵢ of A T A Compute singular values: σᵢ = √λᵢ (in decreasing order) Form V T and Σ from eigenvalues and eigenvectors Compute U from uᵢ = (Avᵢ)/σᵢ for non-zero singular values

This is the written version of the interactive lesson above. See the full Linear Algebra for Machine Learning course.