Dimension Reduction Taxonomy - 2. Matrix Factorization: PCA and SVD

2. Matrix Factorization: PCA and SVD

Principal Component Analysis (PCA) and the Singular Value Decomposition (SVD) are the twin pillars of linear dimensionality reduction. They find linear combinations of the original features that capture the maximum variance. PCA identifies the directions (principal components) that maximize the variance of the projected data. SVD is a robust matrix decomposition that underpins PCA and provides a direct way to compute the components, especially for high-dimensional or sparse matrices.

This diagram illustrates the core mechanism of PCA. In the input space (the 2D plane), points are distributed with a clear elongated shape along the diagonal. PCA finds the direction of maximum variance, labeled PC1 (Principal Component 1), which is the green line. The dashed lines show the orthogonal projections of each point onto PC1. The projected points (green circles on the PC1 axis) are the 1D representation of the data. This projection preserves the spread of the data as much as possible; points that were far apart in the 2D space remain far apart on the PC1 axis. The variance along PC1 is the largest eigenvalue of the covariance matrix. This is why PCA is often used for feature extraction: it finds a new coordinate system that aligns with the inherent structure of the data, allowing us to discard dimensions with low variance (noise) and retain the most informative directions.

2.1 Mathematical Foundations

Given a centered data matrix X of size n × p, PCA seeks a set of k orthonormal vectors (principal components) that maximize the variance of the projected data. The first principal component w is the eigenvector of the covariance matrix X^TX corresponding to the largest eigenvalue. The objective is:

subject to $||w||=1$.

The Singular Value Decomposition (SVD) of X is:

where the columns of V contain the principal components. The variance explained by the i-th component is:

This connection makes PCA numerically stable and allows it to handle n << p.

Derivation of PCA via Lagrange multipliers: To find the first principal component, we maximize $w^{T}Cw$ subject to $w^{T}w=1$, where C = X^TX is the covariance matrix. The Lagrangian is:

Taking the derivative with respect to w yields:

which simplifies to the eigenvalue equation:

Thus, the principal components are the eigenvectors of C, and the variance explained by each is the corresponding eigenvalue λ. Subsequent components are found recursively by deflating the covariance matrix, ensuring orthogonality.

2.2 Variants of PCA

Kernel PCA extends PCA to non-linear spaces via the kernel trick, mapping data into a high-dimensional feature space using a kernel function κ(x, y). The kernel matrix K is computed and centered, and PCA is performed on K, allowing non-linear structure to be captured. Sparse PCA imposes sparsity on the loadings, improving interpretability by selecting a subset of original features. Robust PCA decomposes the matrix into low-rank and sparse components, resisting outliers and gross corruption. Incremental PCA updates components online as new data arrives, and Randomized PCA uses random projections to approximate the SVD for speed.

Each variant addresses a specific limitation of the vanilla PCA. Kernel PCA is powerful for datasets with non-linear manifolds, but it is computationally expensive for large datasets due to the O(n³) cost of eigendecomposition of the kernel matrix. Sparse PCA is favored in genomics and text analysis where interpretability is paramount. Robust PCA is the go-to for surveillance, face recognition, and any domain with severe outliers. Randomized PCA is now a standard preprocessing step for huge datasets, providing a fast approximation with controlled error.

2.3 Example: Student Performance Analysis

If we had grades in Mathematics, Physics, Chemistry, and Literature, PCA could reduce these 4 dimensions to 2 principal components. The first component might represent "Quantitative Ability" (high loadings on Math/Physics/Chem), while the second might represent "Verbal Ability" (high loading on Literature). Plotting students in this 2D space reveals clusters of "STEM-oriented" and "Humanities-oriented" students.

For instance, suppose the covariance matrix has eigenvectors with weights: for PC1, [0.6, 0.6, 0.5, 0.1] and for PC2, [0.1, 0.1, 0.2, 0.9]. A student with high grades in Math, Physics, and Chem but average in Literature will have a high PC1 score and low PC2 score, placing them on the STEM cluster. Conversely, a student with high Literature but lower science scores will have a low PC1 but high PC2. This 2D representation captures the essential academic profile of each student, enabling educators to identify strengths and tailor instruction, while also providing a compact visualization of the entire cohort.

Applications

• Image compression (eigenfaces).
• Genomic data analysis (population structure).
• Financial risk modeling (factor analysis).
• Anomaly detection via reconstruction error.

Strengths and limitations