Definition and Mathematical Formulation
Singular Value Decomposition (SVD) is a fundamental factorization technique in linear algebra, decomposing a matrix into three distinct matrices. For any given real or complex matrix $ M $ of size $ m \times n $, the SVD is expressed as: $$ M = U \Sigma V^*, $$ where:
- $ U $ is an $ m \times m $ unitary (orthogonal if real) matrix, whose columns are the left-singular vectors of $ M $,
- $ \Sigma $ is an $ m \times n $ diagonal matrix with non-negative real entries $ \sigma_1, \sigma_2, \dots, \sigma_p $ (where $ p = \min(m, n) $), called singular values, arranged in descending order,
- $ V^* $ is the conjugate transpose of an $ n \times n $ unitary matrix $ V $, whose columns are the right-singular vectors of $ M $.
The singular values $ \sigma_i $ are the square roots of the eigenvalues of $ M^M $ (or $ MM^ $), where $ M^ $ is the conjugate transpose of $ M $. The matrices $ U $ and $ V $ are unitary, meaning $ U^U = I $ and $ V^*V = I $, where $ I $ is the identity matrix. The decomposition is always possible for any matrix, regardless of shape or rank, distinguishing it from eigenvalue decomposition, which is limited to square matrices.
Computational Methods
The computation of SVD involves reducing the matrix to a bidiagonal form via Householder transformations, followed by iterative QR-like algorithms to diagonalize the bidiagonal matrix. The standard algorithm, developed by Golub and Reinsch in 1970, is numerically stable and widely implemented in software libraries such as LAPACK and MATLAB. For large matrices, modern methods employ randomized algorithms or divide-and-conquer strategies to improve efficiency.
Key computational steps include:
- Bidiagonalization: Transform $ M $ into a bidiagonal matrix using orthogonal (real) or unitary (complex) transformations.
- QR Iteration: Apply QR decomposition iteratively to the bidiagonal matrix to converge to diagonal form.
- Truncation: In practical applications, only the largest $ k $ singular values and corresponding vectors are retained, forming truncated SVD, which reduces computational cost and mitigates noise sensitivity.
The computational complexity of exact SVD is $ O(mn^2) $ for an $ m \times n $ matrix. Truncated SVD, which computes only the top $ k $ components, reduces this to $ O(kmn) $, making it feasible for high-dimensional datasets.
Applications
SVD has broad applications across scientific computing, data analysis, and engineering:
- Data Compression: By retaining only the largest singular values, matrices can be approximated with reduced rank, minimizing storage requirements while preserving essential information. This is used in image and signal compression.
- Principal Component Analysis (PCA): SVD underpins PCA, where the right-singular vectors of a centered data matrix represent principal components, and singular values indicate variance explained by each component.
- **