Unit II Overview: Dimensionality Reduction

High-dimensional data poses fundamental computational and statistical challenges. Dimensionality reduction methods find compact, low-dimensional representations that preserve the most important structure of the data.

The Curse of Dimensionality

Introduced by Bellman (1961), this phenomenon describes how data becomes increasingly sparse in high-dimensional spaces:

• Volume of a hypersphere relative to enclosing hypercube -> 0 as dimensions increase
• K-nearest neighbors become unreliable as all distances converge
• Exponentially more data is needed to maintain the same density

Edge length needed to capture 10% of data in a hypercube: l(d) = 0.1^(1/d)

At d=10, you need ~79% of each dimension's range to capture just 10% of the data.

Why Dimensionality Reduction?

Unit II Roadmap

Two Paradigms

• Feature Selection: Select a subset of original features (interpretable, no transformation)
• Feature Extraction: Create new features as functions of originals (PCA, LDA, ICA)

Exam-Ready Summary

• Curse of dimensionality: data becomes sparse exponentially fast as dimensions grow
• Dimensionality reduction can be supervised (LDA) or unsupervised (PCA)
• Linear methods: PCA, LDA, FA, ICA — fast and interpretable
• Non-linear methods: Kernel PCA, t-SNE, UMAP — powerful but harder to interpret
• Always check how much variance/information is retained after reduction