Principal Component Analysis

Principal Component Analysis, or PCA, replaces each vector with a lower-dimensional representation using a linear transformation.

Programming

Interactive lab

Try it: Principal Component Analysis (2-D → 1-D)

How PCA compresses 2-D points to a 1-D code with , where is the top eigenvector of , recovers them as , and why no other direction has a smaller total squared reconstruction error.

How it works

Optionally centre the data by subtracting the mean.
Form , the sum of ( is the covariance matrix).
Find A's eigenvalues and the unit eigenvector u of the largest one (closed form for a symmetric 2×2 matrix).
Compress each point to and recover on the principal line.
The total squared reconstruction error equals the smaller eigenvalue; compare it with any other direction.

Default run (7 steps): 9 points in 2-D. Goal: a 1-D representation y = W x (W is 1x2) and a recovery x~ = U y that keep the total squared reconstruction error small. … Your direction at 90° (0, 1) would give error 34.8889 — 31.6146 more than PCA's 3.2743. No unit direction beats u.

Simplified: Only 2-D data reduced to one dimension (2–12 points), so the eigenproblem has a closed form; real PCA works with many dimensions and numerical eigen-solvers.

Educational simulation

Loading the simulation…

Why PCA Changes the Representation

A dataset may contain vectors with many features, even when a smaller representation can retain the important structure. Principal Component Analysis, or PCA, replaces each vector with a lower-dimensional representation using a linear transformation. It then evaluates that representation by how well the original vector can be approximately reconstructed.

What happens to a vector as it moves from the original higher-dimensional space into a lower-dimensional PCA space?

Compression and Recovery Spaces

Start with one vector x in R^{^d}. The compression matrix W has n rows and d columns, where n is smaller than d. Multiplying W by x gives y = W x, which belongs to R^{^n}. Because y has fewer coordinates than x, this is the dimensionality-reduction step.

Compression does not by itself restore the original vector. A recovery matrix U has d rows and n columns. Multiplying U by the compact vector gives the recovered vector, written as x-tilde = U y. This recovered vector is again in R^{^d}, but it is generally an approximation rather than an exact restoration of every detail.

How does W map a high-dimensional vector into a lower-dimensional representation, and how does U reconstruct an approximation?

Worked example

Tracking the Vector Shapes

Suppose x has d coordinates and PCA uses n coordinates with n smaller than d. Track the shapes through compression and recovery.

1
Compression matrix
W has n rows and d columns, so W has shape n by d.
2
Compressed representation
Multiplying W by x produces y = W x in R^{^n}. The representation has n coordinates.
3
Recovery matrix
U has d rows and n columns, so U has shape d by n.
4
Recovered vector
Multiplying U by y produces x-tilde = U y in R^{^d}, the same dimensional space as x.

Result

The mapping is R^{^d} to R^{^n} to R^{^d}: x becomes y through W, and y becomes the approximation x-tilde through U.

Building the Two PCA Matrices

Assume X has one row for each example and one column for each original feature. If there are m examples and d features, X has m rows and d columns. Matrix A is formed by multiplying X transposed by X: A = X transposed X. Its dimensions are d by d, so A operates in the feature-dimensional space.

The same matrix A can be understood as combining the examples through outer products. If x_i is the column-vector form of example i, then A is the sum of the outer products x_i x_i transposed. This explains why A is associated with relationships in the feature-dimensional space.

Reverse the multiplication order and define B = X X transposed. Because X has m rows, B is m by m. Its entry in row i and column j is the inner product of x_i and x_j. Thus B records pairwise relationships among examples, while A is formed in the feature-dimensional space.

What dimensions does X transposed X have, and how do the rows and columns of X determine whether A represents relationships among features?

Matrix	Construction	Dimensions	Relationships represented
A	X transposed X	d by d	Feature-dimensional space
B	X X transposed	m by m	Pairwise relationships among examples

The multiplication order determines both the dimensions and the interpretation of the matrix.

Transferring an Eigenvector

The useful connection between A and B comes from their multiplication order. Suppose u is an eigenvector of B with eigenvalue lambda. Then B u = lambda u. Since B equals X X transposed, multiply both sides on the left by X transposed. The left side becomes X transposed X X transposed u. Grouping the first two factors as A gives A X transposed u = lambda X transposed u.

Formula, step by step

B u = lambda u, where B = X X transposed

1
Multiply both sides by X transposed: X transposed B u = lambda X transposed u.
2
Replace B with X X transposed: X transposed X X transposed u = lambda X transposed u.
3
Recognize A = X transposed X: A X transposed u = lambda X transposed u.
4
Therefore X transposed u is an eigenvector direction for A, provided it is nonzero.
5
Normalize the direction to obtain (X transposed u) divided by its norm. The corresponding eigenvalue remains lambda.

If u is an eigenvector of B, how does multiplying it by X transposed produce an eigenvector of A, and what happens to the corresponding eigenvalue?

Choosing the Smaller Eigenproblem

The usual PCA construction works with the d by d matrix A. The source describes eigenvalue calculation for A as having complexity O(d cubed), in addition to O(m d squared) for constructing A. When d is much larger than m, this can be expensive because the feature dimension controls the size of A.

Matrix B is m by m, so it can be the more efficient matrix when the number of features greatly exceeds the number of examples. The workflow is to solve the eigenvector problem in the smaller example-based space and then use X transposed to carry each direction into the feature-based space associated with A.

Which matrix is smaller when the number of samples and features differ, and why can choosing that matrix make PCA computation more efficient?

Worked example

Selecting A or B

A dataset has m examples and d features, with d much larger than m. Which matrix is the more attractive starting point for the eigenvector calculation?

1
Determine the dimensions
A is d by d, while B is m by m.
2
Compare the dimensions
Because d is much larger than m, the example-based matrix B is smaller.
3
Use the eigenvector relationship
Solve the eigenvector problem for B, then multiply an eigenvector by X transposed and normalize it to obtain the corresponding direction for A.

Result

B is the efficient route in this situation because it replaces a d by d eigenproblem with an m by m eigenproblem while preserving a route to the feature-space eigenvectors.

Measuring Reconstruction Quality

PCA does not choose W and U merely because their matrix shapes are compatible. For a dataset containing x1 through xm, each vector is compressed and recovered as x-tilde-i = U W x_i. PCA chooses the pair to minimize the total squared distance between each original vector and its recovered version.

Formula, step by step

1
Begin with an original vector x_i in R^{^d}.
2
Compress it using W to obtain y_i = W x_i in R^{^n}.
3
Recover it using U to obtain x-tilde-i = U y_i = U W x_i in R^{^d}.
4
Measure the squared distance between x_i and x-tilde-i.
5
Choose W and U so the total of these squared distances across the dataset is as small as possible.

How are the original vector, its recovered approximation, and their squared distance connected when PCA chooses the best subspace?

Common Matrix Confusions

Common mistake
Treating A and B as having the same dimensions.
What it looks like
```
A = X transposed X is d by d, whereas B = X X transposed is m by m.
```
Why it fails
The multiplication order determines which dimension is repeated in the resulting square matrix.
Do this instead
Count the columns of X for A and the rows of X for B.
Common mistake
Saying that B represents relationships among features.
What it looks like
B's entry in row i and column j is the inner product of examples x_i and x_j.
Why it fails
B is built in the example-based space.
Do this instead
Associate B with pairwise relationships among examples and A with the feature-dimensional space.
Common mistake
Using X transposed u without explaining its role.
What it looks like
From B u = lambda u, the transferred direction is X transposed u.
Why it fails
The eigenvector of B lives in the example-based space, while A operates in the feature-based space.
Do this instead
State that X transposed carries the direction into the feature-based space, then normalize it.
Common mistake
Assuming recovery always restores x exactly.
What it looks like
x-tilde = U W x is an approximation in R^d.
Why it fails
PCA uses fewer coordinates in the compressed representation, so the recovered vector is judged by its distance from the original.
Do this instead
Describe recovery as approximate and connect it to the squared reconstruction-error objective.

Check Your Reasoning

MEDIUM

A data matrix X has m rows and d columns. Explain the dimensions and roles of A = X transposed X and B = X X transposed. Then describe how an eigenvector u of B can be used to obtain an eigenvector direction for A.

Hints

The rows of X correspond to examples and the columns correspond to features.
For the eigenvector transfer, start from B u = lambda u and multiply by X transposed.
Remember to mention normalization of X transposed u.

Your attempt (not saved)

EASY

Describe the complete path for one vector x: first compression with W, then recovery with U. Include the space containing each intermediate vector and state what PCA minimizes across the dataset.