Dimensionality Reduction

Why Fewer Coordinates Matter

Suppose each data vector has d features. Working with every feature may be unnecessary when a smaller representation can retain the important structure of the data. Dimensionality reduction replaces a vector in a higher-dimensional space with a representation containing fewer coordinates. PCA performs this replacement through a linear transformation and evaluates it by how closely the original vector can later be approximated.

The Compression Step

Start with one vector x in R^d. The compression matrix W has n rows and d columns, with n smaller than d. Multiplying W by x produces y = W x, a vector in R^n. The result y has fewer coordinates than x, so it is the compact representation of the original vector.

y = W x

A Symbolic Compression Trace

Returning to the Original Space

Compression alone gives the smaller vector y. To return to the original dimensional setting, PCA uses a recovery matrix U. This matrix has d rows and n columns. Multiplying U by y produces the recovered vector, written as x_tilde = U y. The recovered vector lies in R^d, like the original x, but it is generally an approximation rather than a claim that every detail of x has been restored exactly.

x_tilde = U y

The Complete Reconstruction Pipeline

The full process has two linear transformations. First, W maps x from R^d into the smaller space R^n. Then U maps y back into R^d. Combining the two equations gives x_tilde = U W x. The result has the same dimensional setting as x, but it is a recovered approximation formed from the lower-dimensional representation.

How PCA Chooses W and U

PCA does not select W and U merely because their shapes are compatible. It chooses the pair so that recovered vectors stay close to the original vectors across the dataset. If the dataset contains vectors x_1 through x_m, each vector is compressed and recovered as x_tilde_i = U W x_i. PCA minimizes the total squared distance between every original vector x_i and its recovered version x_tilde_i.

Minimize the total squared distance between x_i and x_tilde_i, where x_tilde_i = U W x_i for i from 1 through m.

Mistakes to Avoid

• Treating dimensionality reduction as an arbitrary deletion of coordinates.

  The source defines the reduction as a linear transformation using the compression matrix W.

  Fix: Describe the compact representation as y = W x, where W maps R^d to R^n.

• Giving W the wrong dimensions.

  The compression matrix has n rows and d columns.

  Fix: Remember that W has n rows and d columns, with n smaller than d.

• Assuming recovery restores the original vector exactly.

  The recovered vector is generally an approximation of the original vector.

  Fix: Write x_tilde = U y and describe it as a vector in R^d that approximates x.

• Optimizing only the compression matrix.

  PCA chooses the pair W and U so that reconstructed vectors are close to the originals.

  Fix: State the reconstruction as x_tilde_i = U W x_i and include both matrices in the optimization goal.

• Measuring only whether the recovered vector has the right number of coordinates.

  PCA evaluates closeness using the total squared distance between original and recovered vectors.

  Fix: Connect the dimensionality change to the reconstruction-error objective.

Check Your Understanding

1. Dimensionality reduction maps a vector from R^d to R^n through a linear transformation, with n smaller than d. The compression matrix W creates the compact representation y = W x. The recovery matrix U maps y back into R^d as the approximation x_tilde = U y. For a dataset, PCA chooses W and U to minimize the total squared distance between original vectors and their recovered approximations.