Dimensionality Reduction, Principal Component Analysis, and Linear Discriminant Analysis

13.1 Dimensionality Reduction

13.1.1 The Idea: Rows, Columns, and Many Attributes

Most real datasets are tables. The rows are observations; the columns are attributes, which you will also hear called features or input variables — the same thing under three names. One row holds one thing you measured (one person, one customer, one machine), and each column holds one measurement taken on it (age, income, engine temperature). A dataset with $n$ observations and $p$ attributes is an $n\times p$ table: $n$ rows and $p$ columns.

With two attributes, say height and weight, you can plot the whole dataset on a flat scatter diagram and see everything at a glance. Draw a horizontal axis for height in centimetres and a vertical axis for weight in kilograms; every person becomes one dot, and the cloud of dots shows the whole dataset in one picture. With three attributes, a three-dimensional graph still works — you can spin it around and see the points from any angle. Beyond that, drawing the data stops being practical, and every extra attribute makes the analysis more complex. Four, five, or a hundred attributes cannot be drawn on a page, and each extra column adds to the computational cost of every method you run.

Real problems routinely come with thousands of columns. A single gene-expression study measures thousands of genes per sample; a colour image is millions of pixel values; a bank's credit file holds hundreds of indicators per customer. So the question this unit answers is practical: what do you do when your data has far more dimensions than you can visualize?

13.1.2 The Catch: Reduce the Dimension but Keep the Information

Dimensionality reduction means moving from a higher dimension to a lower one — from an $n$-dimensional dataset down to three dimensions, or from three to two, or from two to one. The "dimension" here is the number of attributes: a two-dimensional dataset lives on a flat page, a three-dimensional one lives in space, and every added attribute adds a new axis of the same kind.

Cutting the dimension is only half the job. The moment you reduce, a second question appears: is there any information loss? If reducing from a high dimension to a low one throws away half of the information in the original data, the reduction is pointless. You would have a small dataset that no longer says what the big one said. The real goal is to come down in dimension while keeping the maximum available information intact. A reduction technique is useful only when it does both — fewer dimensions and no meaningful information loss.

Real-world connection: this is not a classroom exercise. Genomics, image processing, finance, and marketing all routinely face datasets with thousands of columns; the ability to compress them to a handful of meaningful axes without losing the signal is what makes many machine learning pipelines feasible at all.

13.1.3 The Two Main Techniques

Two well-known data reduction techniques carry this material: principal component analysis (PCA) and Fisher's linear discriminant analysis (LDA).

Both were worked through on a small two-dimensional example, chosen on purpose. With only two dimensions, the variation of the data and the classification behavior of each algorithm are visible with your own eyes — you can see the cloud of points, the direction it stretches along, and where the classes sit — which is exactly why the examples stay so small, and why the same reasoning extends to larger datasets later. The two-dimensional picture is a scaled-down version of the thousands-of-columns problem from 13.1.1: if you understand which direction to project in two dimensions, you already understand the whole method.

13.2 Principal Component Analysis

13.2.1 What PCA Is

Principal component analysis is a dimensionality reduction technique discovered by Hotelling, a famous statistician, way back in 1933, and today it is used extensively in machine learning algorithms. Its age should not fool you: the idea is so fundamental that modern pipelines still run it as a standard first step.

The objective of PCA is to find the most accurate data representation in a lower dimensional space by projecting the data in the direction of maximum variation. "Projecting" means dropping perpendiculars from every point onto a chosen line (in two dimensions) or plane (in higher dimensions), and reading off where each perpendicular lands. The projection is "most accurate" when the chosen direction captures as much of the spread of the data as possible — the projected points stay far apart, so the view along that direction still distinguishes different observations. How do we identify that direction? By considering the highest eigenvalue.

To follow the reasoning properly you need some linear algebra — above all eigenvalues and eigenvectors — because the math of PCA runs on them. An eigenvector (a direction that a matrix only stretches, never turns), written $a$, and its eigenvalue (how much that direction gets stretched), written $\lambda$, are the two objects the entire method is built on: each principal direction is an eigenvector, and its eigenvalue tells you how much variation that direction carries. That is why matrix courses are the standard prerequisite for this material. Real-world: PCA and LDA sit inside many current machine learning pipelines — from face recognition to finance and genomics — and the linear algebra underneath them is exactly why matrix courses are the standard prerequisite for understanding them.

13.2.2 Orthogonality: From Correlated x's to Uncorrelated z's

Start with original data on two variables, $x_1$ and $x_2$. PCA transforms the data into new variables $z_1$ and $z_2$, called the principal components. The key property is orthogonality: if $x_1$ and $x_2$ are highly correlated, then the transformed $z_1$ and $z_2$ are uncorrelated — no dependency remains between them. The old variables carry overlapping information; the new ones do not, which is what makes them clean building blocks.

Concretely, in the two-dimensional case, $z_1$ and $z_2$ are linear combinations of $x_1$ and $x_2$. Because PCA forces them uncorrelated, the variation of the data cleanly splits between them: whatever variation is not on the first axis sits on the second, with no double counting. Orthogonality, in other words, is what guarantees that the information kept by the reduction is not duplicated.

13.2.3 Why Uncorrelated Components Matter: Multicollinearity

The reason orthogonality matters comes from multiple regression. Suppose $y$ is a function of independent variables, $y=f(x_1,x_2,\dots ,x_n)$, written out as

$$y=b_0+b_1{x}_1+b_2{x}_2+\cdots +b_n{x}_n$$

where $b_0$ is the intercept and $b_i$ is the coefficient of the input $x_i$. Each coefficient says "if $x_i$ goes up by one unit, $y$ changes by $b_i$, with everything else held fixed" — so the whole setup quietly assumes the inputs can be varied independently. The whole setup assumes the inputs are independent, but in practice some of them are highly correlated.

A common stopgap is to inspect the data, pick out which variables are highly correlated, and drop the redundant ones — any input that adds nothing to predicting $y$ is not worth carrying, in computation time or in model terms. That works, but it is a judgement call and it throws information away wholesale. PCA offers a cleaner path: transform the data first. After the transform, the function becomes $y=f(z_1,z_2,\dots ,z_n)$, and the predictive power of $y$ is much better than it was with the raw correlated $x$'s — because the $z$'s are uncorrelated by construction, the regression no longer has to guess which correlated variable caused what. The orthogonality objective is not decoration — it removes a real failure mode of regression.

13.2.4 Reading the Data: Correlation and Variation in Each Direction

Consider a two-dimensional dataset: $n$ measures on two variables, meaning $n$ rows and two columns. After drawing the scatter diagram, one fact stands out: as $x_1$ increases, $x_2$ also increases, so the two variables are related in some sense. To measure how strong that linear relationship is, we compute the correlation matrix between $x_1$ and $x_2$:

$$R=\left[\begin{array}{cc}{r}_{11}& r_{12}\\ r_{21}& r_{22}\end{array}\right]$$

where $r_{11}$ and $r_{22}$ are one, because each variable is perfectly correlated with itself, and $r_{12}$ and $r_{21}$ are the same number, because the correlation of $x_1$ with $x_2$ equals the correlation of $x_2$ with $x_1$. The correlation coefficient $r$ always lies between minus one and plus one: close to +1 means a strong linear relationship; close to −1 means a strong relationship running the other way; near 0 means no linear relationship at all. Looking at this scatter diagram, the guess is that $r$ comes out slightly more than 0.8 — a strong, positive, roughly linear relation. The same table extends to $p$ variables: the correlation matrix then shows the pairwise correlations of all the variables.

Beyond the correlation matrix, we also look at how the data spreads. In this two-dimensional case there are two possible directions of variation: the variation along the $x_1$ direction and the variation along the $x_2$ direction. Looking at the scatter, both spreads are substantial and similar — neither beats the other by much, so you cannot ignore either direction, and the $x_1$–$x_2$ picture does not yet tell us where to project.

To quantify these spreads we use the covariance matrix:

$$S=\left[\begin{array}{cc}{s}_{11}& s_{12}\\ s_{21}& s_{22}\end{array}\right]$$

its top-left position holds the variation of $x_1$, its bottom-right position holds the variation of $x_2$, and the off-diagonal positions hold the covariation between $x_1$ and $x_2$. The two are related: the covariance $s_{12}$ divided by the two standard deviations gives the correlation $r_{12}$, so covariance carries the same direction information but in the raw units of the data — which is why variables measured on wildly different scales produce covariance matrices dominated by the large-unit variable. Software returns this matrix directly; the concept behind each entry is what we just described.

13.2.5 Rotating the Axes: From x1, x2 to z1, z2

With only two dimensions, the most we can reduce is from two to one. Along the way, the two resulting variables must stay independent. The move, as described in the earlier discussion: instead of thinking in the $x_1$ and $x_2$ directions, rotate the $x_1$ axis anticlockwise by an angle $\theta$, rotate the $x_2$ axis by the same angle $\theta$, and call the new axes $z_1$ and $z_2$. The angle is ours to choose. The rotation is a standard change of axes:

$$\left(\begin{array}{c}{z}_1\\ z_2\end{array}\right)=\left(\begin{array}{cc}\cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$$

Let us read this equation carefully. Each new variable is a weighted sum of the old ones: $z_1=x_1\cos \theta +x_2\sin \theta$ and $z_2=-x_1\sin \theta +x_2\cos \theta$. The matrix multiplies a column vector of old coordinates on the right, so it is the standard anticlockwise rotation of the coordinate axes: a point's new coordinate along $z_1$ is its old coordinate projected onto the rotated axis. The minus sign on $-\sin \theta$ is what makes the two new axes perpendicular, no matter which $\theta$ we pick — and perpendicular axes are exactly the uncorrelated, non-redundant frame PCA wants. (If the minus sign sat in the other entry, the same matrix would rotate the points instead of the axes, and the first principal component would come out mirrored.)

After the rotation, the same scatter plot redrawn on the $z_1$–$z_2$ axes shows something the $x$-axes could not: the variation along $z_1$ is far larger than the variation along $z_2$. Two conclusions follow in one move. First, $z_1$ and $z_2$ are highly uncorrelated — the orthogonality objective is met. Second, $z_1$ alone is enough to carry the maximum variation, and with it the maximum information, of the original data; along $z_2$ there is so little variation that it can be ignored. The whole business of PCA is captured in that picture: one rotated axis that carries nearly everything, one that carries almost nothing.

13.2.6 The Recipe: Covariance Matrix, Characteristic Equation, Eigenvalues, Eigenvectors

The order of the steps is the logic of the method: the data's spread lives in the covariance matrix, the eigenvalues of that matrix rank the candidate directions by how much variation they carry, and the eigenvectors actually draw those directions. Notice what this gives us: one short recipe replaces the eyeballing that worked in two dimensions but is impossible with a thousand columns. The next section runs this recipe on a two-dimensional dataset, step by step.

13.3 Worked Example: PCA on a Two-Dimensional Dataset

13.3.1 The Given Covariance Matrix

The example uses a simple two-dimensional dataset along $x_1$ and $x_2$; the scatter plot again shows a near-linear relationship. Instead of asking for the covariance matrix to be built from raw data, the matrix is given directly:

$$S=\left[\begin{array}{cc}1.15& 5.76\\ 5.76& 29.54\end{array}\right]$$

The top-left entry 1.15 is the variation (variance) of $x_1$; the bottom-right entry 29.54 is the variance of $x_2$; the two off-diagonal entries, both 5.76, are the covariance between $x_1$ and $x_2$. The task: find where the data varies the most, using this matrix.

Two readings of the matrix are worth making before any calculation. First, the covariance is large compared with the variances, which means the two variables move together strongly — dividing the covariance 5.76 by the product of the two standard deviations, $\sqrt{1.15}\times \sqrt{29.54}\approx 5.83$, gives a correlation of about 0.99, a very strong positive linear relationship consistent with the near-linear scatter. Second, $x_2$ varies about 25 times more than $x_1$ (29.54 against 1.15), so any single-axis view that ignores $x_2$'s spread would throw most of the variation away. Real-world: software does the eigen arithmetic for you — a one-line R documentation example shows how to get the eigenvalues of such a matrix directly — but the steps below show what that one line is really doing.

13.3.2 The Characteristic Equation and Its Determinant

To find where the variation is largest, we solve the famous characteristic equation — the determinant of $S$ minus $\lambda$ times the identity matrix equals zero:

$$|S-\lambda I|=0$$

Here $S$ is the covariance matrix, $\lambda$ (lambda) is an eigenvalue, and $I$ is the 2 by 2 identity matrix:

$$I=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

We write $\lambda I$ rather than a plain $\lambda$ because subtracting a bare number from a matrix is not defined — each diagonal position of $S$ has to lose its own $\lambda$. So a 2 by 2 matrix gives two solutions for $\lambda$, one per diagonal entry, and each solution needs its own position on the diagonal. Substituting the numbers:

$$\left|\begin{array}{cc}1.15-\lambda & 5.76\\ 5.76& 29.54-\lambda \end{array}\right|=0$$

13.3.3 The Quadratic Equation and the Quadratic Formula

Expanding the determinant — multiplying the two binomials, subtracting, and collecting terms — produces a simple quadratic equation:

The roots of any quadratic equation $a{\lambda }^2+b\lambda +c=0$ come from the quadratic formula: minus $b$, plus or minus the square root of $b$ squared minus $4ac$, over $2a$:

$$\lambda =\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$

13.3.4 The Two Eigenvalues

Solving the quadratic gives two eigenvalues:

$${\lambda }_1=30.66,{\lambda }_2=0.0258$$

For convenience, the smaller value can be truncated to 0.03.

13.3.5 Eigenvectors and the Principal Directions

Each eigenvalue comes with an eigenvector. The second famous equation solves for the eigenvector $a_j$ belonging to the eigenvalue ${\lambda }_j$:

$$(S-{\lambda }_{j}I)a_j=0$$

where $a_j$ is the column vector $(a_{11},a_{12})$. The equation says: when the matrix $S$ acts on this direction, the result is ${\lambda }_j$ times the direction itself — the direction is only stretched, never turned. Take $\lambda =30.66$ first and solve the system; the solution gives the line of the first principal component — the $z_1$ direction onto which the data is projected.

Repeat with the small eigenvalue, about 0.03, and you get the second eigenvector, the $z_2$ direction. The full computation runs exactly as before, so it is worth seeing once:

13.3.6 Variance Explained: The 99 Percent Story

Now we can say how much of the total variation each principal component explains. The proportion of the total variation carried by component $i$ is its eigenvalue divided by the sum of all eigenvalues:

$$\frac{{\lambda }_1}{{\lambda }_1+{\lambda }_2}\text{for PC1},\frac{{\lambda }_2}{{\lambda }_1+{\lambda }_2}\text{for PC2}$$

The logic: the sum of the eigenvalues is the total variation (the trace check from 13.3.4), and each eigenvalue is the amount of variation its own component carries — so the ratio is the share of the total.

This number justifies the reduction. Because $z_1$ carries almost all of the variation, we can retain $z_1$ and ignore $z_2$ for further analysis: the two-dimensional dataset collapses to one dimension with the information intact. Visually, draw a bar chart of the eigenvalues: the horizontal axis names the two components (PC1, PC2), the vertical axis is the eigenvalue. The first bar reaches 30.66 — nearly the full height of the chart — while the second bar is a sliver of 0.03 at the base. That picture is the whole story of the reduction: one towering bar, one sliver, so keep the tall one.

13.3.7 The Reduction Decision Rule

The same reasoning scales to $p$ dimensions. From $p$ original variables, build principal components $z_1,z_2,\dots ,z_p$. Keep adding components until their eigenvalues together explain about 90 percent of the total variation; the remaining components can be ignored in further calculations. In this worked example the first component alone cleared the bar with room to spare (99.9 percent), so the rule says: keep one, drop the rest.

13.4 Linear Discriminant Analysis

13.4.1 Maximum Variation Is Not Always Useful for Classification

LDA stands for linear discriminant analysis, and it is often called Fisher's linear discriminant. The central contrast sits right here: PCA hunts for the direction of maximum variation, while LDA hunts for the direction that separates classes. The simple numerical example made the point: the direction of maximum variation can be useless for classification. Data projected along the direction of greatest spread can still leave the classes overlapping — maximum variation and maximum separation are different goals.

Think of two groups of points, each shaped like a small cloud. The overall dataset may stretch along one long axis — the direction of maximum variation — but if both clouds happen to lie side by side along that axis, their projections onto it overlap completely and you cannot tell which cloud a point came from. Meanwhile a much shorter direction, one that points across the gap between the two clouds, separates them perfectly. That is the failure PCA can have as a classification tool, and the motivation for LDA: it maximizes the variation between the two classes and minimizes the variation within each class, which is the same between-versus-within logic that cluster analysis will reuse later.

Pick PCA when you need a compact, uncorrelated description of the data itself; pick LDA when the whole point is to tell the classes apart.

13.4.2 Between-Class and Within-Class Variation

Think of LDA's goal as a ratio: make the spread between the classes as large as possible while the spread inside each class stays as small as possible. When the between-class variation is large and the within-class variation is small, the classes sit far apart as compact clouds, and a straight line can separate them. Each class should be a tight cluster, and the two clusters should be far apart; the line that best separates them cuts through the empty space between the clusters.

In the small example used in the lecture, the numerical problem was shown to make the PCA-versus-LDA contrast visible; the detailed calculation of how that separating line is derived — the full mathematical walkthrough — was left for the next session, where the same two-dimensional dataset is worked from the data up.

13.5 Cluster Analysis

13.5.1 The Preview: Inter-Cluster and Intra-Cluster Distance

Cluster analysis is a technique for combining observations into clusters, so that similar observations end up in similar groups. The questions it answers: how do we group the data, and what is the minimum number of clusters needed? Unlike PCA and LDA, cluster analysis starts with no labels at all: the algorithm looks at the raw positions of the observations and groups the ones that sit close together.

The logic mirrors LDA: maximize the inter-cluster distance, the separation between different clusters, and minimize the intra-cluster distance, the spread inside each cluster. The more separated the clusters are, the more easily you can see distinct groups at the higher dimensional level; the tighter each cluster is, the more meaningful the grouping — every member of a cluster really is like its neighbours, and every cluster really is different from the others.

The reference material for the course names a cluster analysis book as the source for this method — the technique is standard and well documented, and the preview here only marks the territory the following session will explore on its own dataset. Real-world connection: this is exactly how customer databases are segmented — a travel company, for instance, can group its past customers by age, travel preferences, and spending so that each segment receives its own targeted offer, which is a far more effective use of a marketing budget than sending every offer to everyone.

13.5.2 What Comes Next

Two items were planned for the following session: the full LDA worked problem on a two-dimensional dataset, including the mathematics of how the separating line is found, and the cluster analysis discussion with its own dataset. Both stay on two dimensions so the variation and the classification behavior remain visible — the same reason the PCA example stayed two-dimensional in 13.3.

13.6 Student Questions and Answers

13.6.1 Standardizing the Data Before PCA

For context, here is what the answer will have to weigh when the discussion resumes. Standardizing a variable means rescaling it so that it has mean 0 and variance 1: subtract the variable's mean and divide by its standard deviation, written $z=\frac{x-\bar{x}}{s}$. Every variable then contributes on the same footing, and PCA is run on the correlation matrix of the data rather than the raw covariance matrix.

The tension is the same one flagged for cluster analysis in 13.5.1. A variable measured in large units — say income in thousands — will dominate the covariance matrix, and the first principal component will be dragged toward it, not because it carries more information but simply because its numbers are bigger. Standardizing prevents that. But standardization also changes the meaning of the components: when all variables have variance 1, the total variation is just the number of variables, and the components reflect structure rather than scale. When all the original variables are already on the same scale and units, the choice matters far less. Whichever way the discussion resolves it, the two sides of the argument are on the table: raw units can bias the components toward big-number variables, while standardization can erase genuine differences in variation between variables.

Exam Guidance Summary

• The exam expects no full eigenvalue calculation; the worked example only shows the path behind the concept. The heavy arithmetic exists to make the method visible, not to be reproduced — understand the route from covariance matrix to characteristic equation to eigenvalues, do not memorize the arithmetic.
• Answer only what the question requires, and address whichever part is relevant; do not add computation the question does not ask for. A question about the concept needs the concept, not a re-run of the worked example.
• The LDA numerical problem will be simple: no extensive math to calculate, no functions or derivatives involved, and nothing like that is expected for calculation in the exam. Expect the idea — the between-versus-within ratio and the contrast with PCA — rather than heavy computation.
• Hold onto the PCA-versus-LDA contrast: the direction of maximum variation is not the same as the direction of classification separation. This single contrast connects the two main techniques of the unit and is the safest concept to be tested on.
• Remember the decision rule and its limit: keep principal components until about 90 percent of the total variation is explained, and recognize when that rule cannot apply — comparable shares, like 40 percent and 60 percent, make any reduction unsafe.
• A revision session was planned to revisit the full material before the end of the term; the standardization question from 13.6 was deferred to that following session and is worth revisiting too.

Key Industry Applications

• Real-world: PCA and LDA are used extensively in machine learning algorithms today, and the linear algebra underneath them is the standard prerequisite for understanding them. PCA remains a standard preprocessing step in modern pipelines — in face recognition (where the leading principal components of images are known as eigenfaces), in genomics (thousands of genes per sample), and in finance (hundreds of indicators per customer).
• Real-world: high-dimensional datasets with thousands of columns are routine in practice — gene-expression studies, image data, and customer databases all fit this shape — which is exactly the situation dimensionality reduction is built for: compress the columns without losing the signal.
• Real-world: multicollinearity is a real regression failure mode, and transforming correlated inputs into uncorrelated principal components is one standard way to avoid it. Regression models fitted on the transformed components no longer fight over which correlated variable caused which effect.
• Real-world: the R documentation example computes eigenvalues and eigenvectors in one line; in practice the software does the arithmetic, and the concept is what you need to understand. The same applies across statistical packages: the output is the eigenvalues and the components, and the analyst's job is to read them.
• Real-world: LDA's class-separating line is used wherever group membership must be predicted from measurements — a restaurant chain can tell prospective buyers from non-buyers, a bank can separate good from bad credit risk, and marketers can map how customers perceive competing brands.
• Real-world: cluster analysis — maximizing inter-cluster separation and minimizing intra-cluster spread — is the standard way to group similar observations. Customer relationship management (CRM) teams use it to segment customers so each segment gets its own targeted offer, which is the same grouping-by-distance logic previewed in this lecture.