Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

PCA and LDA

Principal Component Analysis (PCA) finds directions of maximal variance for dimensionality reduction; Linear Discriminant Analysis (LDA) finds directions that best separate labelled classes by maximising between-class to within-class scatter.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

PCA and LDA are linear dimensionality‑reduction methods an engineer uses to reduce feature count, speed up models, and improve generalisation. PCA is unsupervised and preserves directions of largest variance; LDA is supervised and preserves directions that best separate class labels (useful before classifiers or for visualization).

Key ideas

  • Goal: find orthonormal directions (principal components) w₁, w₂, … such that projections of data on these directions have maximal variance and the components are mutually orthogonal.

  • Assumptions: data are centred (mean subtracted). If not centred, PCA finds directions for the covariance about the origin (usually undesirable). PCA makes no class/label assumptions. When feature scales differ, standardise features (z-score) or use the correlation matrix; otherwise large-scale features can dominate the components.

  • Variance maximisation derivation (standard asked derivation):

    1. Let Σ be the empirical covariance matrix of centred data: Σ = (1/(n-1)) Σ_{i=1..n} x_i x_i^T.
    2. For a unit vector w (w^T w = 1), the variance of projections {w^T x_i} is w^T Σ w.
    3. Choose w to maximise w^T Σ w subject to w^T w = 1. Set up Lagrangian L(w, λ) = w^T Σ w − λ(w^T w − 1).
    4. Stationary condition: ∂L/∂w = 2Σw − 2λw = 0 ⇒ Σw = λw. Thus w is an eigenvector of Σ; λ is its eigenvalue equal to the variance along w.
    5. Ordering eigenvectors by decreasing eigenvalue gives principal components.
  • Alternate view (reconstruction error): choosing k principal components minimises mean squared reconstruction error when approximating x by its projection onto the k‑dimensional subspace spanned by top k eigenvectors. This equivalence is shown by expanding squared error and using orthogonality.

  • Computation: either eigen-decomposition of Σ or singular-value decomposition (SVD) of centred data matrix X_c: X_c = U S V^T; columns of V are principal directions.

  • Linear Discriminant Analysis (LDA, Fisher LDA)

    • Goal: find a linear projection w that maximises separation between labelled classes. For two classes, one common criterion is Fisher’s criterion: maximise the ratio of between-class variance to within-class variance after projection.
    • Definitions:
      • For class c with n_c samples, mean m_c = (1/n_c) Σ_{x in class c} x.
      • Global mean m = (1/n) Σ_{i=1..n} x_i.
      • Within-class scatter S_W = Σ_{c} Σ_{x in class c} (x − m_c)(x − m_c)^T. (measures dispersion inside classes)
      • Between-class scatter S_B = Σ_{c} n_c (m_c − m)(m_c − m)^T. (measures separation of class means)
    • Fisher criterion: choose w to maximise J(w) = (w^T S_B w) / (w^T S_W w).
    • Two-class closed form: for two classes, the optimal direction (up to scale) is w ∝ S_W^{-1} (m_1 − m_2). This follows by differentiating J(w) or solving the generalised eigenproblem.
    • Multiclass LDA: the solution reduces to solving the generalised eigenvalue problem S_B w = λ S_W w. Keep the eigenvectors corresponding to largest eigenvalues. Note S_W must be non-singular; if singular (common in high-dimensional small-sample problems) use regularisation or PCA first.
    • Assumptions and limits: LDA implicitly assumes classes are Gaussian with equal covariance matrices (homoscedastic). If covariances differ strongly or class distributions are non‑Gaussian, LDA may be suboptimal. LDA is translation invariant; subtracting any global mean does not affect S_W or S_B.
  • Relationship and usage notes

    • PCA is unsupervised; it may discard directions useful for class discrimination. Use PCA before LDA when d ≫ n or S_W is singular.
    • LDA reduces dimensionality to at most C−1 dimensions for C classes (since rank(S_B) ≤ C−1). PCA yields at most min(n−1, d) nonzero principal components because rank(Σ) ≤ min(n−1, d).
  • What to draw for exams

    • For PCA: draw a 2D scatter of centred data points, draw covariance ellipse aligned to principal axes, draw principal direction vectors w₁ and w₂ (label eigenvalues λ₁ ≥ λ₂). Show projection of points on w₁.
    • For LDA (two classes): draw two clusters, mark class means m₁ and m₂, draw within-class scatter ellipses, draw discriminant line (w) that maximises projected separation and show projected means and overlap.

Formulas

Σ = (1/(n-1)) Σ_{i=1..n} (x_i − μ)(x_i − μ)^T — Σ is empirical covariance matrix; x_i are feature vectors (units: same as outer product of feature units, e.g., m^2 if features in metres); μ is sample mean; applies when data are centred or for sample covariance.

max_{w, w^T w = 1} w^T Σ w — optimisation problem that defines the first principal component; w is unit vector (dimensionless unit: direction in feature space); applies to centred data.

Σ w = λ w — eigenvalue problem; λ is variance along principal component w (units: square of feature units); applies when Σ is symmetric positive semi-definite.

X_c = U S V^T — SVD of centred data matrix X_c (n×d); columns of V are principal directions; singular values s_i relate to eigenvalues by λ_i = s_i^2/(n-1) when using sample covariance. Explained variance ratio for top k PCs: R_k = (∑{i=1..k} λ_i)/(∑{i=1..r} λ_i), where r = rank(Σ).

S_W = Σ_c Σ_{x∈c} (x − m_c)(x − m_c)^T — within-class scatter (units: squared feature units); applies for labelled data.

S_B = Σ_c n_c (m_c − m)(m_c − m)^T — between-class scatter (units: squared feature units); m is global mean.

J(w) = (w^T S_B w) / (w^T S_W w) — Fisher criterion; unitless ratio; maximised by LDA.

S_B w = λ S_W w — generalised eigenproblem for multiclass LDA; w are discriminant directions; applies when S_W is non-singular (otherwise regularise).

w ∝ S_W^{-1} (m_1 − m_2) — closed form for two-class LDA (direction up to scale); applies for two classes with invertible S_W.

Worked examples

Example 1 — PCA on a small 2D dataset Data (unitless): x1 = [2, 0], x2 = [0, 1], x3 = [−1, 0]. Steps:

  1. Compute sample mean μ = (1/3)([2,0] + [0,1] + [−1,0]) = [1/3, 1/3].
  2. Centre data: x1_c = [1.6667, −0.3333], x2_c = [−0.3333, 0.6667], x3_c = [−1.3333, −0.3333].
  3. Compute sample covariance Σ = (1/(n−1)) Σ x_i_c x_i_c^T.
    • Sum outer products = [[4.6667, −0.3333], [−0.3333, 0.6667]].
    • Σ = (1/2)·that = [[2.33335, −0.16665], [−0.16665, 0.33335]].
  4. Solve eigenproblem Σ w = λ w. The eigenvalues are approximately λ1 = 2.34715, λ2 = 0.31955. Corresponding unit eigenvector for λ1 ≈ [0.997, −0.0825].
  5. Project centred points onto first principal component w: projections ≈ [1.6889, −0.3873, −1.3016] (sum ≈ 0). Final answer: principal direction w ≈ [0.997, −0.0825], first principal variance ≈ 2.347 (unit: squared units of original features).

Example 2 — Two-class LDA in 2D Data (unitless): class 1 points: a1=[2,0], a2=[3,0]; class 2 points: b1=[0,1], b2=[0,2]. Steps:

  1. Class means: m1 = [2.5, 0], m2 = [0, 1.5]. Global mean m = [1.25, 0.75].
  2. Within-class scatter S_W:
    • For class1: deviations are [−0.5,0] and [0.5,0] ⇒ sum outer = [[0.5,0],[0,0]].
    • For class2: deviations are [0,−0.5] and [0,0.5] ⇒ sum outer = [[0,0],[0,0.5]].
    • S_W = [[0.5,0],[0,0.5]].
  3. Between-class scatter S_B:
    • m1 − m = [1.25, −0.75], m2 − m = [−1.25, 0.75].
    • For each class multiply outer by n_c = 2 and sum: S_B = [[6.25, −3.75], [−3.75, 2.25]].
  4. Solve generalised eigenproblem S_B w = λ S_W w. Since S_W is diagonal, S_W^{-1} = [[2,0],[0,2]]. Then S_W^{-1} S_B = [[12.5, −7.5], [−7.5, 4.5]]. Eigenvalues are 17 and 0; top eigenvector proportional to [−1.6667, 1] ⇒ normalized w ≈ [−0.857, 0.515].
  5. Project means onto w to find separation: w^T m1 ≈ −2.1425, w^T m2 ≈ 0.7725 (difference ≈ 2.9150) showing good separation. Final answer: LDA direction w ≈ [−0.857, 0.515] (unitless direction), providing maximal Fisher separation.

Common mistakes

  • Using PCA to reduce dimensionality before a classifier without checking whether discarded components contained class-discriminative information.
  • For LDA, forgetting that maximum possible LDA dimensions ≤ C − 1 where C is number of classes.
  • Trying to invert S_W when S_W is singular (common when d > n); require regularisation or prior PCA.
  • Mixing up S_W and S_B formulas or forgetting the factor n_c in S_B.

For your exam

Typical question types

  • Definitions: define PCA, principal components, covariance matrix, LDA, within/between scatter.
  • Short notes: compare PCA vs LDA, assumptions of LDA, why centre data for PCA.
  • Derivations: derive Σ w = λ w from variance maximisation; derive w ∝ S_W^{-1} (m1 − m2) for two-class LDA; show PCA minimises reconstruction error.
  • Numericals: compute mean, covariance, eigenvalues/eigenvectors for small datasets; compute S_W, S_B and LDA direction for small labelled sets.
  • Diagrams: plot 2D data, mark principal directions and projections; for LDA show projected class overlap. What full marks answers include
  • All definitions written clearly (bold term defined, units noted if needed).
  • Show steps with formulas and small algebra (set up Lagrangian, show derivative, obtain eigenproblem).
  • For numericals: show intermediate arithmetic (means, centred points, covariance entries), eigenvalues/eigenvectors (approx), and final projection values with units or "unitless".

Quick check

  1. Why must you usually subtract the mean before applying PCA?
  2. For C classes, what is the maximum number of independent LDA projection directions? (Answer in words is fine.)
  3. Give the two-matrix eigenproblem that you solve to get multiclass LDA directions. Answers: 1) To make covariance meaningful (PCA maximises variance about the mean); if not centred principal directions shift and are incorrect. 2) At most C − 1 independent LDA directions. 3) S_B w = λ S_W w.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?