Matrix Multiplication
Dimensionality reduction maps vectors from R^d to R^n using a linear transformation, where n is smaller than d.
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.
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.
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.
Identify the input space: Since x has 3 coordinates, it is a vector in R^3.
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.
Count the output coordinates: The product y = W x has one coordinate for each row of W. Therefore y has 2 coordinates.
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.
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.
Compress: Compute y = W x. The result has 2 coordinates because W has 2 rows.
Recover: Compute x̃ = U y. The result has 3 coordinates because U has 3 rows.
Interpret: The recovered vector has the same dimensionality as x, but it is an approximation of x rather than a guaranteed exact copy.
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.
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
Treating W as if it increases the number of coordinates.
The product W x has one coordinate for each row of W, so it has n coordinates and belongs to R^n.
Fix:
Read the number of rows in W as the number of coordinates in the compressed result.Assuming that U restores the original vector exactly.
Having the same dimensionality as x does not mean that every detail of x has been restored.
Fix:
Describe U y as an approximation of x unless exact equality has been established.Choosing W and U only because their dimensions are compatible.
PCA evaluates the pair by the total squared distance between original and recovered vectors.
Fix:
Connect matrix selection to reconstruction quality across the dataset.Describing compression without mentioning recovery.
The smaller vector explains the representation, but PCA's objective also depends on reconstructing an approximation with U.
Fix:
Trace the complete path x to y to x̃ when explaining PCA.
Check Your Understanding
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.
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: 4
The product has one coordinate for each row of W. Therefore y has 4 coordinates, even though x has 7.
The Complete Transformation
- Dimensionality reduction maps a vector from R^d to R^n through a linear transformation, with n smaller than d.
- The compression matrix W has n rows and d columns and produces y = W x in R^n.
- The recovery matrix U has d rows and n columns and produces x̃ = U y in R^d.
- The recovered vector has the original dimensionality but is generally an approximation.
- 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.