The Hong Kong University of Science and Technology · FACULTY OF COMPUTER SCIENCE

MAIE5421 Chap.7 Dimensionality Reduction with PCA and LDA

- one subject, every graph, every model, every mark
8 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 7 of 10 · MAIE5421

Dimensionality Reduction with PCA and LDA

Why reduce dimensions at all

Feature sets built by hand usually contain redundancy. We tend to include every factor we can think of, and the correlations between features are often hidden, so two measurements may say almost the same thing, as the lecture's pair of temperatures recorded in two neighbouring districts of Hong Kong shows.

When one feature is a linear combination of others, the data has no spread at all in some direction; more commonly the spread in some directions is small compared with others.

Dropping the low-spread directions loses little information and makes every later computation cheaper.

Principal component analysis

PCA looks for a set of orthogonal directions, measures the variance of the data along each, keeps the ones that account for most of the variance and discards the rest, then re-expresses the data in the kept directions. The lecture shows that eigenvalue analysis does exactly this.

The data is centred by subtracting the mean, the D by D covariance matrix is computed, and its eigenvalue decomposition gives orthogonal eigenvectors as the directions and eigenvalues as the variance along each.

Taking the K eigenvectors with the largest eigenvalues, with K chosen by accumulating eigenvalues until enough variance is covered, forms a projection matrix, and each centred sample is mapped to K new coordinates.

Linear discriminant analysis

LDA also reduces dimension, but it uses class labels to make the reduced data separate the classes well.

It defines a within-class scatter matrix, which measures how compact each class is around its own mean, and a between-class scatter matrix, which measures how far the class means lie from the overall mean.

It then seeks the linear transformation under which the between-class scatter is as large as possible relative to the within-class scatter, measured through their determinants and solved by a generalised eigenvalue decomposition. At most c - 1 directions are useful for c classes, because that many axes suffice to define the hyperplanes that separate them.

In this chapter

What this chapter covers

  • 01

    Redundant and correlated features

  • 02

    Variance by direction as a measure of expressiveness

  • 03

    The five ideas behind PCA

  • 04

    Centring, covariance and eigenvalue decomposition

  • 05

    Choosing K from accumulated eigenvalues

  • 06

    Projecting data onto principal components

  • 07

    Within-class and between-class scatter in LDA

  • 08

    Why LDA keeps at most c minus one directions

Worked example · free

Project five points onto their first principal component and measure what is lost

Q [7 marks]. AskSia-authored practice. The points (1, 2), (2, 1), (3, 4), (4, 3) and (5, 5) have covariance eigenvalues 3.6 and 0.4, with leading eigenvector (1, 1)/√2. Project each point onto the first component, reconstruct the point (1, 2) from its projection, and show that the mean squared reconstruction error equals the discarded eigenvalue. The marks shown are an AskSia study allocation and are not the University's marking scheme.
Five centred points and their two principal directions.Five centred points and their two principal directions. The blue axis carries an eigenvalue of 3.6 and the orange one 0.4, so projecting each dot onto the blue axis, along the dashed segments, keeps 90% of the variance.PC1, λ = 3.6PC2, λ = 0.4x (centred)y (centred)Dots: data pointsBlue: projectionsPC1 keeps 90%
Five centred points and their two principal directions. The blue axis carries an eigenvalue of 3.6 and the orange one 0.4, so projecting each dot onto the blue axis, along the dashed segments, keeps 90% of the variance.
  • 2Centre on the mean (3, 3) and project with z = (x + y)/√2: -2.12, -2.12, 0.71, 0.71, 2.83.
  • 2Reconstruct (1, 2): z = -2.12 gives -2.12 × (1, 1)/√2 = (-1.5, -1.5), plus the mean = (1.5, 1.5).
  • 2Squared errors along the second direction: 0.5, 0.5, 0.5, 0.5 and 0, total 2.
  • 1Mean squared error 2 / 5 = 0.4, the discarded eigenvalue.
The one-dimensional coordinates are -2.12, -2.12, 0.71, 0.71 and 2.83. Reconstructing the first point from its coordinate gives (1.5, 1.5), half a unit away from (1, 2) in each direction, a squared error of 0.5. Four of the points lose 0.5 and the point (5, 5) loses nothing because it lies on the first component, so the mean squared error is 0.4. That equals the eigenvalue that was discarded, which is the general meaning of an eigenvalue in PCA: the variance you give up by dropping its direction.
Sia tip — When you drop components, add up the eigenvalues you discard and divide by the total. That fraction is the share of variance your reduced data no longer contains.
Glossary

Key terms

Dimensionality Reduction
Reducing the number of variables describing each sample, by selecting existing features or by building new ones.
Covariance Matrix
The D by D matrix of variances and covariances of the centred features, whose eigenvectors PCA uses as directions.
Eigenvalue
In PCA, the variance of the data along the corresponding eigenvector of the covariance matrix.
Projection Matrix
The D by K matrix whose columns are the kept eigenvectors, used to map each centred sample to K coordinates.
Within-class Scatter
The summed spread of each class around its own mean, the compactness term in LDA.
Between-class Scatter
The spread of the class means around the overall mean, the separation term in LDA.
Linear Discriminant Analysis
A supervised reduction method that chooses directions maximising class separation relative to within-class spread.
FAQ

Dimensionality Reduction with PCA and LDA FAQ

What is the difference between PCA and LDA?

PCA is unsupervised and keeps the directions along which the data varies most, regardless of class. LDA is supervised and keeps the directions that best separate the classes relative to their internal spread. PCA can keep any number of components up to the original dimension, while LDA can keep at most one fewer than the number of classes.

How do I decide how many principal components to keep?

Sort the eigenvalues in decreasing order and add them up until the running total reaches the share of variance you want to preserve, such as 90% or 95%. The lecture describes choosing K by accumulating the sum of eigenvalues in this way. The number of eigenvalues you needed is K, and the projection matrix holds the matching eigenvectors as its columns.

Why must data be centred before PCA?

Because the covariance matrix measures spread around the mean. If the mean is not subtracted first, the leading direction tends to point towards the mean of the data rather than along its spread, and the eigenvalues no longer equal the variance along each direction. Centring is therefore the first of the lecture's five calculation steps.

Study strategy

Assessment move

Take a five-point, two-feature dataset and do the whole PCA by hand: centre, compute the two variances and the covariance, find both eigenvalues, project, and check that the projected variance equals the leading eigenvalue. Then sketch two labelled clouds for which the first principal component mixes the classes, and mark the direction LDA would choose instead.

Working through Dimensionality Reduction with PCA and LDA in MAIE5421? Sia is AskSia’s AI Computer Science tutor — ask any MAIE5421 Dimensionality Reduction with PCA and LDA question and get a clear, step-by-step explanation grounded in how MAIE5421 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your MAIE5421 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works