At its core, dimensionality reduction is the quest to find a lower-dimensional subspace that preserves the maximum amount of information from the original data. Imagine a clouds of data points in a 3D space; if these points roughly form a flat pancake, we can project them onto a 2D plane without losing much detail. The goal is to identify the 'principal axes' of the data—directions along which the data varies the most. This is where Eigenvalues and Singular Value Decomposition (SVD) become indispensable, as they allow us to mathematically quantify the importance of different directions in a high-dimensional vector space.
To understand this, we first look at Eigen-decomposition. For a square, symmetric matrix $C$ (such as a covariance matrix), the eigenvalue equation is defined as $C v = \\lambda v$. Here, $v$ is the eigenvector and $\\lambda$ is the eigenvalue. Geometrically, $v$ represents a direction that remains unchanged in orientation when transformed by $C$, and $\\lambda$ represents the scaling factor. In the context of dimensionality reduction, if $C$ is the covariance matrix of our data, the eigenvector corresponding to the largest eigenvalue $\\lambda_{max}$ is the direction of maximum variance. By keeping only the top $k$ eigenvectors, we project our data onto a $k$-dimensional subspace that captures the most significant patterns.
While Eigen-decomposition is limited to square matrices, Singular Value Decomposition (SVD) generalizes this power to any $m \\× n$ matrix $A$. SVD factorizes $A$ into three distinct matrices: $A = U \Sigma V^T$. Here, $U$ is an $m \\× m$ orthogonal matrix whose columns are the left-singular vectors, $V$ is an $n \\× n$ orthogonal matrix whose columns are the right-singular vectors, and $\\Sigma$ is a diagonal matrix containing the singular values $\\sigma_i$ in descending order. These singular values are the square roots of the eigenvalues of $A^T A$, effectively telling us how much 'energy' or variance is captured along each principal axis.
The relationship between SVD and Principal Component Analysis (PCA) is profound. PCA is typically performed by computing the covariance matrix $C = \frac{1}{n-1} X^T X$ (where $X$ is centered data) and finding its eigenvectors. However, performing SVD directly on $X$ is numerically more stable and efficient. If we apply SVD to $X$, the right-singular vectors $V$ are exactly the principal components (the eigenvectors of $X^T X$), and the singular values $\\sigma_i$ relate directly to the variance explained by each component via the formula $\\lambda_i = \frac{\\sigma_i^2}{n-1}$.
To perform actual dimensionality reduction, we use the concept of low-rank approximation. According to the Eckart-Young-Mirsky theorem, the best rank-$k$ approximation of a matrix $A$ (in terms of Frobenius norm) is obtained by setting all singular values $\\sigma_i = 0$ for $i > k$. We construct a truncated matrix $\\Sigma_k$ and compute $A_k = U \Sigma_k V^T$. This process discards the 'noise'—the directions with the smallest singular values—and retains the 'signal,' drastically reducing the size of the dataset while minimizing the reconstruction error $\\|A - A_k\\|_F$.
In summary, Eigen-decomposition provides the foundation for understanding variance via covariance matrices, while SVD provides a universal framework to decompose any data matrix into its constituent geometric rotations and scales. By analyzing the spectrum of singular values, we can decide exactly how many dimensions to keep to balance the trade-off between compression and information loss. This mathematical duality transforms a massive table of numbers into a structured set of principal axes, allowing us to visualize and process high-dimensional data with surgical precision.