Matrix Multiplication

The compression matrix W has n rows and d columns, where n is smaller than d.

Programming

Why Reduce Dimensions

A vector can contain many features, but working with every feature is not always necessary when a smaller representation can retain important structure. Dimensionality reduction addresses this by mapping a vector from a higher-dimensional space to a lower-dimensional space. In PCA, the mapping is linear, and the reduced representation is evaluated by how well the original vector can later be approximated.

How does a vector with d coordinates move through a linear transformation and become a vector with n coordinates when n is smaller than d?

The Compression Step

Start with a vector x in R^{^d}. The compression matrix W has n rows and d columns, where n is smaller than d. Matrix multiplication produces y = W x. Because W has n rows, the result y has n coordinates, so y belongs to R^{^n}. The number of coordinates has been reduced from d to n.

How do the rows and columns of W and the input vector determine the number and meaning of the output coordinates?

Worked example

A Three-Coordinate Vector Becomes Two Coordinates

Use a compression matrix W with 2 rows and 3 columns on a vector x with 3 coordinates.

1
Identify the input space
Since x has 3 coordinates, it is a vector in R^{^3}.
2
Identify the matrix shape
W has 2 rows and 3 columns, so it has the required shape for multiplying a 2-by-3 matrix by a 3-coordinate vector.
3
Count the output coordinates
The product y = W x has one coordinate for each row of W. Therefore y has 2 coordinates.

Result

The transformation maps x from R^{^3} to y in R^{^2}. The representation is shorter because it contains 2 coordinates instead of 3.

The Recovery Step

Compression produces the smaller vector y, but PCA also defines a way to return to the original dimensional setting. The recovery matrix U has d rows and n columns. Multiplying U by y produces the recovered vector, written as x̃ = U y. The recovered vector belongs to R^d, just as the original x does. However, it is generally an approximation: returning to the original number of coordinates does not claim that every detail of x has been restored exactly.

How does the recovery matrix U transform the compressed representation back into an approximation of the original vector?

Worked example

Compression Followed by Recovery

A vector x begins in R^{^3}. A compression matrix W maps it to y in R^{^2}. A recovery matrix U then maps y back into the original three-dimensional space.

1
Compress
Compute y = W x. The result has 2 coordinates because W has 2 rows.
2
Recover
Compute x̃ = U y. The result has 3 coordinates because U has 3 rows.
3
Interpret
The recovered vector has the same dimensionality as x, but it is an approximation of x rather than a guaranteed exact copy.

Result

The complete path is x to y to x̃: first from R^{^3} to R^{^2}, then from R^{^2} back to R^{^3}.

Reconstruction Error in PCA

PCA does not choose W and U only because their shapes are compatible. It chooses them so that the recovered vectors are close to the original vectors across the dataset. For a dataset containing vectors x1 through xm, each vector is compressed and recovered as x̃i = U W xi. PCA minimizes the total squared distance between every original vector xi and its recovered version x̃i.

How are the original vector x and recovered vector U(Wx) compared, and what quantity is minimized when their squared distance is reduced?

The optimization connects compression and recovery. W controls the move into the smaller space, U controls the move back into the original space, and the quality of the pair is judged by reconstruction error. Across the dataset, the desired pair makes the total squared distance between each xi and U W xi as small as possible.

Mistakes with the Two Matrices

Common mistake
Treating W as if it increases the number of coordinates.
What it looks like
W has n rows and d columns, with n smaller than d, and x has d coordinates.
Why it fails
The product W x has one coordinate for each row of W, so it has n coordinates and belongs to R^{^n}.
Do this instead
Read the number of rows in W as the number of coordinates in the compressed result.
Common mistake
Assuming that U restores the original vector exactly.
What it looks like
After computing x̃ = U y, the recovered vector has d coordinates.
Why it fails
Having the same dimensionality as x does not mean that every detail of x has been restored.
Do this instead
Describe U y as an approximation of x unless exact equality has been established.
Common mistake
Choosing W and U only because their dimensions are compatible.
What it looks like
A pair of matrices can produce the products W x and U y.
Why it fails
PCA evaluates the pair by the total squared distance between original and recovered vectors.
Do this instead
Connect matrix selection to reconstruction quality across the dataset.
Common mistake
Describing compression without mentioning recovery.
What it looks like
Stopping after y = W x.
Why it fails
The smaller vector explains the representation, but PCA's objective also depends on reconstructing an approximation with U.
Do this instead
Trace the complete path x to y to x̃ when explaining PCA.

Check Your Understanding

MEDIUM

Suppose x has d coordinates, W has n rows and d columns, and U has d rows and n columns, where n is smaller than d. Describe the spaces containing x, y = W x, and x̃ = U y. Then explain why PCA evaluates W and U using the squared distance between x and x̃.

Hints

Use the number of coordinates in each vector to identify its space.
Use the rows of W and U to determine the output dimensions.
Remember that x̃ is obtained by first compressing with W and then recovering with U.

Your attempt (not saved)

What do you think happens?

If W has 4 rows and x has 7 coordinates, how many coordinates does y = W x have?

Reveal answer

Answer:

The product has one coordinate for each row of W. Therefore y has 4 coordinates, even though x has 7.

The Complete Transformation

1
Dimensionality reduction maps a vector from R^{^d} to R^{^n} through a linear transformation, with n smaller than d.
2
The compression matrix W has n rows and d columns and produces y = W x in R^{^n}.
3
The recovery matrix U has d rows and n columns and produces x̃ = U y in R^{^d}.
4
The recovered vector has the original dimensionality but is generally an approximation.
5
PCA chooses W and U to minimize the total squared distance between original vectors and their recovered versions.

Key Takeaways

W compresses x from R^{^d} into y in R^{^n}, where n is smaller than d.
The number of rows in W determines the number of coordinates in the compressed vector.
U maps the compressed vector back into R^{^d}, producing an approximation of the original vector.
PCA evaluates the pair W and U by minimizing total squared reconstruction distance across the dataset.

Related concepts

More concepts starting with M