LDA for Dimensionality Reduction

PCA vs LDA: Unsupervised vs Supervised

Both PCA and LDA project data into a lower-dimensional subspace.

However, their underlying goals are completely different:

  PCA (Unsupervised - Ignores Class Labels):      LDA (Supervised - Uses Class Labels):
  Finds directions of MAXIMUM TOTAL VARIANCE.      Finds directions of MAXIMUM CLASS SEPARATION.
     ▲                                                ▲
     │  (o) (o)                                       │  (o) (o)  Class 1
     │ (o)    (x)                                     │ ───────► MAXIMUM CLASS SEPARATION!
     │       (x) (x)                                  │  (x) (x)  Class 2
  ───┴─────────────────► Feature X1                   └───┴─────────────────► Feature X1

If you apply PCA to data where class separation lies along a low-variance direction, PCA will accidentally wipe out your class signals!

LDA uses target labels $y$ to preserve classification signals.

Fisher's Linear Discriminant Criterion

Fisher (1936) defined the optimal projection direction $w$ as the vector that maximizes between-class variance while minimizing within-class variance:

$$J(w) = \frac{w^T S_B w}{w^T S_W w}$$

1. Between-Class Scatter Matrix ($S_B$): Measures the distance between class mean vectors ($\mu_1 - \mu_2$).

$$S_B = (\mu_1 - \mu_2)(\mu_1 - \mu_2)^T$$

2. Within-Class Scatter Matrix ($S_W$): Measures the variance spread of data points within each individual class.

$$S_W = \sum_{x \in C_1} (x - \mu_1)(x - \mu_1)^T + \sum_{x \in C_2} (x - \mu_2)(x - \mu_2)^T$$

Maximizing $J(w)$ forces data points in the same class to cluster tightly together ($S_W \to 0$) while pushing class means far apart ($S_B \to \text{Max}$).

  Maximizing J(w) = ( Between-Class Distance )^2 / ( Within-Class Variance Spread )

Dimensionality Constraint: At Most $C - 1$ Components

Because LDA relies on class means to construct the Between-Class Scatter matrix $S_B$:

For a classification problem with $C$ classes, $S_B$ has rank at most $C - 1$.

Therefore, LDA can project data into at most $C - 1$ dimensions:

• Binary Classification ($C = 2$): Reduces data to 1 single dimension.
• 10-Class Problem ($C = 10$): Reduces data to at most 9 dimensions.

Assumptions of LDA

1. Gaussian Distribution: Each class features are normally distributed.
2. Homoscedasticity: All classes share the same covariance matrix $\Sigma$. If classes have significantly different covariance matrices, use Quadratic Discriminant Analysis (QDA) instead.

Say this out loud

LDA is a supervised dimensionality reduction algorithm that projects data onto axes maximizing between-class variance while minimizing within-class variance using Fisher's criterion. Unlike unsupervised PCA, LDA uses target labels to preserve class separability. For C classes, LDA can extract at most C minus 1 linear discriminant components.

Followups to expect

1. What is Quadratic Discriminant Analysis (QDA)? A non linear extension of LDA that drops the assumption of shared covariance matrices, allowing each class to estimate its own covariance matrix $\Sigma_k$, producing quadratic decision boundaries.
2. What happens if feature count d is larger than sample count N (Small Sample Size problem)? Within-class scatter matrix $S_W$ becomes singular and non-invertible. Apply PCA first to reduce $d < N$ before running LDA.