At its core, dimensionality reduction is the art of finding a lower-dimensional subspace that preserves the most critical information of a high-dimensional dataset. Imagine a 3D cloud of points that mostly lies along a flat tilted plane; we can describe these points more efficiently using only two coordinates on that plane rather than three in space. The mathematical goal is to identify the 'principal axes' of the data—the directions along which the data varies the most. By projecting data onto these axes, we filter out noise and redundancy, retaining only the signals that define the underlying structure.
To formalize this, we begin with the concept of Eigenvalues and Eigenvectors. For a square, symmetric matrix $C$ (such as a covariance matrix), an eigenvector $v$ is a non-zero vector that, when multiplied by $C$, results only in a scaling of $v$. This is expressed as: $$Cv = \\lambda v$$ where $\\lambda$ is the eigenvalue. In the context of dimensionality reduction, the eigenvectors of the covariance matrix $\\Sigma$ represent the directions of maximum variance, and the corresponding eigenvalues $\\lambda$ quantify the amount of variance captured along each direction. A large $\\lambda$ indicates a 'principal component' that holds significant information.
While Eigendecomposition requires a square matrix, Singular Value Decomposition (SVD) generalizes this to any $m \\× n$ matrix $A$. SVD decomposes $A$ into three constituent matrices: $$A = U \Sigma V^T$$ Here, $U$ is an $m \\× m$ orthogonal matrix containing the left singular vectors, $V^T$ is the transpose of an $n \\× n$ orthogonal matrix containing the right singular vectors, and $\\Sigma$ is an $m \\× n$ diagonal matrix containing the singular values $\\sigma_i$ in descending order. Essentially, SVD tells us that any linear transformation can be broken down into a rotation, a scaling, and another rotation.
The profound link between SVD and Eigenvalues emerges when we examine the product $A^T A$. If we substitute the SVD definition, we get: $$A^T A = (V \Sigma^T U^T)(U \Sigma V^T) = V (\Sigma^T \Sigma) V^T$$ Since $U^T U = I$, the resulting matrix is the Eigendecomposition of $A^T A$. The columns of $V$ are the eigenvectors of $A^T A$, and the squared singular values $\\sigma_i^2$ are the eigenvalues $\\lambda_i$. This means SVD provides a direct path to Principal Component Analysis (PCA) without explicitly computing the covariance matrix, which is numerically more stable for large datasets.
To perform dimensionality reduction, we employ the 'Truncated SVD' approach. Since the singular values in $\Sigma$ are ordered $\sigma_1 \\≥ \sigma_2 \\≥ \dots \\≥ \sigma_n$, we can approximate the original matrix $A$ by keeping only the top $k$ singular values and setting the rest to zero: $$A_k = U_k \Sigma_k V_k^T$$ This low-rank approximation minimizes the Frobenius norm $\\|A - A_k\\|_F$, effectively discarding the dimensions that contribute the least to the total variance. This process transforms the data into a compressed format while retaining the 'skeleton' of the original signal.
In practice, this mathematical framework enables everything from image compression to latent semantic analysis (LSA) in NLP. By projecting a high-dimensional vector $x$ onto the first $k$ columns of $V$, we obtain a reduced representation $z = V_k^T x$. This projection removes the 'noise' associated with smaller eigenvalues, allowing machine learning models to generalize better by avoiding the curse of dimensionality. By mastering SVD and Eigen-analysis, we move from treating data as a collection of numbers to treating it as a geometric structure that can be simplified and understood.