svd

Singular value decomposition (SVD) is a factorization of a real or complex matrix that expresses the matrix as a product of three simpler matrices. For A in R^{m×n}, the SVD writes A = U Σ V^T (or A = U Σ V^* in the complex case), where U is an m×m orthogonal (or unitary) matrix, V is an n×n orthogonal (or unitary) matrix, and Σ is an m×n diagonal (more precisely, rectangular diagonal) matrix with nonnegative real numbers on its diagonal.

The diagonal entries of Σ are the singular values, usually arranged in nonincreasing order: σ1 ≥ σ2 ≥ … ≥ σp ≥ 0, where p = min(m,n). The columns of U and V are called the left and right singular vectors, respectively. In reduced or compact SVD, A ≈ U_r Σ_r V_r^T, with U_r ∈ R^{m×r}, Σ_r ∈ R^{r×r}, and V_r ∈ R^{n×r}, for some r ≤ p.

Key relationships: the nonzero singular values squared are the eigenvalues of A^T A and of A A^T. Specifically, A^T A has eigenvectors given by the columns of V with eigenvalues σ_i^2, and A A^T has eigenvectors given by the columns of U with the same eigenvalues. The SVD provides a canonical form of A and is unique up to signs of singular vectors corresponding to distinct positive singular values.

Interpretation and uses: the singular values measure how A stretches space along the corresponding singular vectors. The SVD yields the best rank-k approximation to A in both Frobenius and spectral norms (Eckart–Young theorem), making it central to dimensionality reduction, data compression, noise reduction, PCA, solving ill-posed problems, and recommender systems. Computationally, it is obtained via Golub–Kahan bidiagonalization or related iterative methods, with complexity O(min(mn^2, m^2n)) for full decompositions.