Singular Value Decomposition (SVD)

The SVD is a universal factorization that exists for any real or complex matrix, regardless of its shape, rank, or condition. For any matrix A of dimensions m × n, there exists a decomposition A = U Σ V^T (or A = U Σ V^H for complex matrices), where:

• U is an m × m orthogonal/unitary matrix.
• Σ is an m × n rectangular diagonal matrix with non-negative real entries (the singular values).
• V^T is the transpose of an n × n orthogonal/unitary matrix V.

While the singular values themselves are uniquely determined for a given matrix, the singular vectors in U and V are unique only up to sign flips for non-degenerate singular values, and up to unitary transformations within subspaces corresponding to repeated singular values.

The Eckart–Young–Mirsky theorem establishes SVD's optimality for low-rank approximation. For a given matrix A and target rank k, the best rank-k approximation A_k in both the Frobenius norm and the spectral norm is obtained by the truncated SVD. This is done by:

• Taking the full SVD: A = U Σ V^T.
• Keeping only the k largest singular values in Σ, setting the rest to zero to form Σ_k.
• Forming the approximation: A_k = U Σ_k V^T.

This property is foundational for lossy compression and denoising, as it guarantees that discarding smaller singular values minimizes the reconstruction error. The approximation error is precisely the square root of the sum of squares of the discarded singular values for the Frobenius norm.

SVD explicitly constructs the four fundamental subspaces of a matrix, providing deep geometric insight:

• Column Space (Range): Spanned by the first r columns of U, where r is the rank of A. These are the left singular vectors corresponding to non-zero singular values.
• Null Space (Kernel): Spanned by the last (n - r) columns of V. These are the right singular vectors corresponding to zero singular values.
• Row Space: Spanned by the first r columns of V.
• Left Null Space: Spanned by the last (m - r) columns of U.

The singular values quantify the energy or importance of each direction in these subspaces. This property is crucial for solving linear systems, understanding system controllability/observability, and performing tasks like latent semantic analysis (LSA) in NLP, where the column space of a term-document matrix represents concepts.

The SVD provides the most reliable numerical tool for diagnosing the stability and invertibility of a matrix. The condition number of a matrix A, denoted κ(A), is defined as the ratio of its largest to smallest singular value: κ(A) = σ_max / σ_min.

• A large condition number (e.g., > 10^12) indicates the matrix is ill-conditioned. Small perturbations in the input can cause large, unstable variations in the output, making problems like linear regression numerically challenging.
• A condition number near 1 indicates well-conditioning.
• Rank deficiency is revealed by singular values that are exactly zero (or, in practice, smaller than a numerical tolerance). This property is essential for ridge regression (Tikhonov regularization), which directly adds a constant to the singular values to improve condition number and solution stability.

SVD produces orthonormal bases for the row and column spaces, which have desirable invariance properties:

• Unitary Invariance: The singular values of a matrix are invariant under unitary (orthogonal) transformations. For any unitary matrices P and Q, the matrix P A Q^H has the same singular values as A. This makes SVD robust to rotations and reflections.
• Scale Invariance (of subspaces): While singular values scale with the matrix norm, the relative directions of the principal components (the columns of U and V) are invariant to uniform scaling of the data.
• Connection to Eigen-decomposition: For a symmetric positive semi-definite matrix A, the SVD and eigen-decomposition coincide: U = V and Σ contains the eigenvalues. More generally, the squares of the singular values of A are the eigenvalues of A^T A and A A^T. These properties make SVD the preferred method over eigen-decomposition for general rectangular matrices and for applications like the PCA of a covariance matrix.

The structure of SVD enables significant computational savings and parameter reduction, which is the core of its application in model compression:

• Parameter Count: A dense m × n weight matrix has m × n parameters. Its rank-k approximation via SVD stores U (m × k), Σ (k values), and V^T (k × n), totaling k(m + n + 1) parameters. For k << min(m, n), this represents massive compression.
• Computational Complexity: Matrix-vector multiplication A x costs O(mn). Using the factorized form (U (Σ (V^T x))) costs O(k(m + n)), which is far cheaper for low-rank matrices.
• Progressive Reconstruction: The truncated SVD offers a graceful trade-off between fidelity and compression. Each additional singular value/vector pair incrementally improves the approximation, allowing precise control over the compression-accuracy Pareto frontier. This makes SVD a cornerstone technique for compressing fully-connected and convolutional layers (via reshaping filters) in neural networks for on-device deployment.

Truncated SVD is the practical application of SVD for low-rank approximation and model compression. It retains only the top-k largest singular values and their corresponding singular vectors, discarding the rest. This directly creates a rank-k approximation of the original weight matrix.

• Mechanism: Given a matrix A with SVD A = UΣVᵀ, the truncated version is Aₖ = Uₖ Σₖ Vₖᵀ, where only the first k columns of U and V and the first k singular values in Σ are kept.
• Purpose: Drastically reduces the parameter count and computational cost for matrix-vector multiplications in neural network layers.
• Trade-off: Introduces an approximation error bounded by the Eckart–Young theorem, which states this is the optimal rank-k approximation under the Frobenius and spectral norms.

Principal Component Analysis (PCA) is a closely related dimensionality reduction technique. For a centered data matrix X, PCA is performed via the eigenvalue decomposition of the covariance matrix XᵀX or via the SVD of X itself.

• Mathematical Link: The principal components are the right singular vectors (V) from the SVD of the centered data matrix X = UΣVᵀ. The eigenvalues of the covariance matrix are the squares of the singular values (σ²).
• Key Difference: While SVD is a general matrix factorization, PCA is a specific application of SVD (or eigen-decomposition) for finding orthogonal directions of maximum variance in data. In model compression, PCA principles inspire low-rank approximations of weight matrices.

The Eckart–Young–Mirsky theorem provides the theoretical foundation for using Truncated SVD in compression. It formally guarantees that the best low-rank approximation of a matrix is given by its truncated SVD.

• Formal Statement: For a matrix A and any matrix B of rank at most k, the minimum approximation error ||A - B|| (in either the Frobenius norm or spectral norm) is achieved by B = Aₖ, the truncated SVD retaining the k largest singular values.
• Implication for ML: This theorem justifies SVD as the optimal linear method for compressing weight matrices when measured by these norms. It sets a benchmark for other low-rank factorization techniques.

The nuclear norm (or trace norm) is the sum of a matrix's singular values (||A||_* = Σ σ_i). It serves as a convex surrogate for the non-convex matrix rank function, enabling efficient optimization for low-rank solutions.

• Role in Optimization: In problems like low-rank matrix completion or robust PCA, the rank constraint is replaced with nuclear norm minimization, which can be solved via convex optimization techniques.
• Connection to SVD: The proximal operator for the nuclear norm is singular value thresholding, which applies soft-thresholding to the singular values from an SVD. This makes SVD a core subroutine in algorithms solving nuclear norm regularized problems.

Randomized SVD is a class of algorithms that compute an approximate truncated SVD for very large matrices more efficiently than classical methods. It is essential for applying low-rank techniques to massive weight matrices in modern LLMs.

• Core Idea: Uses random projection to identify a subspace that captures the matrix's range. A small matrix is formed by projecting the original onto this random subspace, and a standard SVD is computed on this smaller matrix.
• Advantage: Offers significant computational savings and reduced memory footprint, especially when only a modest number of singular values/vectors are needed. The error is probabilistic but controllable.
• Use Case: Enables feasible low-rank approximation of layers in billion-parameter models where full SVD is computationally prohibitive.

Tucker decomposition and Tensor-Train (TT) decomposition are higher-order generalizations of SVD for compressing tensors (multi-dimensional arrays), which naturally represent the weights of convolutional or multi-layer perceptron networks.

• Tucker Decomposition: Generalizes SVD by factorizing a tensor into a core tensor multiplied by a factor matrix along each mode. The multilinear rank is controlled by the size of this core. Higher-Order SVD (HOSVD) is a common algorithm to compute it.
• Tensor-Train Decomposition: Represents a high-dimensional tensor as a chain of interconnected low-rank core tensors. It mitigates the "curse of dimensionality" for parameter storage.
• Application: Directly used for neural network compression by applying these decompositions to the 4D weight tensors of convolutional layers, achieving high compression rates.