At its core, dimensionality reduction is the quest to find a lower-dimensional representation of data that preserves as much essential information as possible. Imagine a cloud of points in 3D space that roughly forms a flat pancake; while the data exists in three dimensions, the 'true' structure is effectively 2D. The intuition behind Singular Value Decomposition (SVD) and Eigen-decomposition is to identify the directions (axes) along which the data varies the most. By projecting data onto these principal axes and discarding those with minimal variance, we can compress information without losing the underlying signal.
To understand the machinery, we start with Eigen-decomposition. For a square, symmetric matrix $C$ (such as a covariance matrix), an eigenvector $v$ and its corresponding eigenvalue $\\lambda$ satisfy the equation: $$Cv = \\lambda v$$ Here, $v$ represents a direction that remains invariant under the transformation $C$, and $\\lambda$ scales the magnitude of the vector in that direction. In the context of data, the eigenvector associated with the largest eigenvalue points in the direction of maximum variance, providing the primary component of the data's structure.
While Eigen-decomposition is limited to square matrices, Singular Value Decomposition (SVD) generalizes this to any $m \\× n$ matrix $A$. SVD factorizes $A$ into three distinct matrices: $$A = U \Sigma V^T$$ Where $U$ is an $m \\× m$ orthogonal matrix (left singular vectors), $\\Sigma$ is an $m \\× n$ diagonal matrix containing singular values $\\sigma_i$, and $V^T$ is the transpose of an $n \\× n$ orthogonal matrix (right singular vectors). The singular values in $\\Sigma$ are the square roots of the eigenvalues of $A^T A$ and are ordered such that $\\sigma_1 \ge \\sigma_2 \ge \dots \ge \\sigma_k \ge 0$.
The relationship between SVD and Principal Component Analysis (PCA) is profound. PCA is typically performed by computing the eigen-decomposition of the covariance matrix $C = \frac{1}{n-1} X^T X$ (where $X$ is centered). However, SVD allows us to achieve the same result directly on the data matrix $X$ without explicitly computing the covariance matrix. The right singular vectors $V$ are exactly the principal components, and the singular values $\\sigma_i$ relate to the variance explained by each component via the formula: $$ ext{Variance}_i = \frac{\\sigma_i^2}{n-1}$$
To perform dimensionality reduction, we employ the Eckart-Young-Mirsky theorem, which suggests that the best low-rank approximation of a matrix is obtained by keeping the top $k$ singular values and setting the rest to zero. By truncating the SVD to $A_k = U_k \Sigma_k V_k^T$, we project the original high-dimensional space onto a $k$-dimensional subspace. This effectively filters out 'noise' (represented by small singular values) and retains the 'signal' (represented by large singular values), resulting in a compressed version of the dataset that maintains its geometric integrity.
In conclusion, the transition from eigenvalues to SVD allows us to handle arbitrary data shapes and uncover the latent semantic structure of a dataset. Whether we are compressing images, reducing noise in gene expression data, or building latent semantic indexing for text, we are essentially using the geometry of linear transformations to distinguish importance from irrelevance. The ability to decompose a complex system into its fundamental singular components remains one of the most powerful tools in the machine learning practitioner's arsenal.