PCA: Dimensionality Reduction and Feature Extraction

Why Dimensionality Reduction?

High-dimensional data presents fundamental challenges that degrade both computational efficiency and model performance. The curse of dimensionality manifests in several critical ways.

The Curse of Dimensionality

As dimensionality increases:

1. Volume Explosion: The volume of the feature space grows exponentially as , where is the range of each feature
2. Data Sparsity: For a fixed number of observations , the density of data points vanishes:
3. Distance Concentration: In high dimensions, the ratio of distances between nearest and farthest points converges to 1:

1. Overfitting Risk: Models with many parameters relative to observations generalize poorly

Benefits of Dimensionality Reduction

• Computational Efficiency: Reduces time complexity from to where
• Noise Filtering: Removes low-variance components containing primarily noise
• Visualization: Projects high-dimensional data into 2D/3D for human interpretation
• Multicollinearity Removal: Creates orthogonal features that are uncorrelated
• Improved Generalization: Reduces model complexity and overfitting

PCA Algorithm — Step by Step

PCA finds orthogonal directions of maximum variance in the data through eigendecomposition of the covariance matrix.

Mathematical Formulation

Given a dataset with observations and features:

Step 1 — Center the data:

Step 2 — Compute the covariance matrix:

Step 3 — Eigendecomposition:

where are eigenvalues and are corresponding eigenvectors.

Step 4 — Project data onto principal components:

where contains the top eigenvectors.

Geometric Interpretation

Eigendecomposition and SVD

Relationship Between PCA and Eigendecomposition

The covariance matrix is symmetric positive semi-definite, guaranteeing real non-negative eigenvalues and orthogonal eigenvectors:

where and .

SVD-Based PCA

For computational efficiency, PCA is typically performed via Singular Value Decomposition:

where:

• : left singular vectors (orthonormal)
• : diagonal matrix of singular values
• : right singular vectors (principal directions)

Connection to eigenvalues:

The principal component scores are:

Eigenvector Visualization

Variance Explained and Scree Plot

Proportion of Variance Explained

Each principal component captures a fraction of the total variance:

The cumulative variance explained by the first components:

Scree Plot

The scree plot displays eigenvalues in descending order, showing the "elbow" where adding more components yields diminishing returns.

Choosing the Number of Components

Three principal methods guide component selection:

1. Kaiser's Rule (Eigenvalue > 1)

Retain components where (for standardized data):

Rationale: A component with explains less variance than a single original variable.

2. Cumulative Variance Threshold

Select such that cumulative PVE exceeds a threshold :

Common thresholds: .

3. Scree Plot Elbow Method

Identify the "elow" in the scree plot — the point where the rate of decrease sharply changes:

4. Parallel Analysis (Horn's Method)

Compare eigenvalues to those from random data of the same dimensions. Retain components where:

This method corrects for the upward bias in eigenvalues due to finite sample sizes.

PCA for Visualization (2D/3D)

From High Dimensions to 2D

PCA enables visualization of high-dimensional datasets by projecting onto the first two or three principal components while preserving maximum variance.

Information Loss: When projecting from dimensions to :

2D Projection Example

Kernel PCA for Non-Linear Data

Limitation of Standard PCA

Standard PCA assumes linear relationships. For non-linear manifolds, PCA may fail to capture the intrinsic structure.

The Kernel Trick

Kernel PCA maps data to a higher-dimensional feature space via a non-linear mapping , then performs PCA in .

The key insight: we never compute explicitly. Instead, we use the kernel function:

Common Kernel Functions

Kernel PCA Algorithm

1. Compute the kernel matrix:
2. Center the kernel matrix:
3. Solve the eigenvalue problem:
4. Project onto kernel principal components:

Comparison: Linear vs Kernel PCA

Implementation in Python

Standard PCA with Scikit-Learn

Scree Plot and Component Selection

2D Visualization with Class Labels

Reconstruction from Principal Components

Kernel PCA Implementation

Incremental PCA for Large Datasets

PCA as Preprocessing for Other Models

Before/After PCA Dimensionality Reduction

Mathematical Properties of PCA

Optimality of PCA

PCA finds the rank- approximation that minimizes the reconstruction error:

By the Eckart-Young-Mirsky Theorem, the solution is given by the truncated SVD:

with optimal reconstruction error:

Properties of Principal Components

1. Orthogonality: for
2. Unit length:
3. Maximum variance: is maximized subject to
4. Uncorrelated scores: (diagonal)
5. Total variance preserved:

Common Pitfalls and Best Practices

Pitfalls

When to Use PCA

• Preprocessing: Reduce dimensionality before classification/regression
• Visualization: Project to 2D/3D for exploratory data analysis
• Noise reduction: Remove low-variance components (assumed noise)
• Feature decorrelation: Create uncorrelated features for models assuming independence
• Multicollinearity: Resolve correlated predictors in linear models

When NOT to Use PCA

• Interpretability needed: PCs are linear combinations, not original features
• Sparse data: Use truncated SVD or NMF instead
• Non-linear structure: Use Kernel PCA, t-SNE, or UMAP
• Categorical data: Use MCA (Multiple Correspondence Analysis) instead
• Time series: Use specialized methods (e.g., DMD, POD)

PCA vs Other Dimensionality Reduction Methods

Summary

PCA is the foundational technique for dimensionality reduction:

1. Core idea: Find orthogonal directions of maximum variance via eigendecomposition of the covariance matrix
2. Computational method: SVD is preferred numerically — gives principal directions as columns of
3. Component selection: Use Kaiser's rule, cumulative PVE threshold, or parallel analysis
4. Variance explained: quantifies information retention
5. Optimality: PCA minimizes mean squared reconstruction error (Eckart-Young theorem)
6. Kernel extension: Kernel PCA handles non-linear data via the kernel trick
7. Best practice: Always standardize data, validate reconstruction quality, and choose based on the application's information needs