Concepts / Linear Transformations

Linear Transformations

Dimensionality reduction maps vectors from R^d to R^n using a linear transformation, where n is smaller than d.

  • Programming

Why Fewer Coordinates Can Help

Suppose each vector in a dataset has d features. Working with every feature can be unnecessary when a smaller representation can retain the important structure of the data. Dimensionality reduction addresses this by replacing each vector with a representation that has fewer dimensions. In PCA, this replacement is a linear transformation followed by a reconstruction process, so the reduced representation is judged by how closely the original vectors can be approximated.

Definition

Dimensionality reduction maps vectors from Rd to Rn using a linear transformation, where n is smaller than d.

R^d d coordinatesxoriginal vectorR^n n coordinatesycompact representationcontainscontainslinear mapping
What changes when a vector with d coordinates is mapped into a space with n coordinates, where n is smaller than d?

The Compression Step

Start with one vector x in Rd. 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 Rn. Because n is smaller than d, y contains fewer coordinates than x. This move from Rd to Rn is the central dimensionality-reduction step.

Worked example

Tracking the dimensions

Consider an original vector x in R4. Let W have 2 rows and 4 columns. Determine the space containing the compressed representation y = W x.

  1. 1
    Identify the original vector

    The vector x has four coordinates, so it belongs to R4.

  2. 2
    Inspect the compression matrix

    W has 2 rows and 4 columns. Its 4 columns match the four coordinates of x, and its 2 rows determine the number of coordinates in the result.

  3. 3
    Determine the result

    Multiplying W by x produces y with two coordinates. Therefore y belongs to R2.

Result

The transformation compresses x from R4 into y in R2. The representation has fewer coordinates than the original.

xR^d Wn rows, d columnsyR^n Ud rows, n columnsx̃R^d approximationinputW xcompressed inputU y
How does a vector move from the original space through compression and back to an approximate reconstruction?

The Recovery Step

Compression alone gives the smaller vector y. PCA also describes how 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. This recovered vector lies in R^d, just as the original x does, but it is generally an approximation rather than a claim that every detail of x has been restored exactly.

Worked example

Returning to the original space

A compressed vector y belongs to R2. Let U have 4 rows and 2 columns. Determine the space containing the recovered vector x̃ = U y.

  1. 1
    Identify the compressed input

    The compressed representation y has two coordinates and belongs to R2.

  2. 2
    Inspect the recovery matrix

    U has 2 columns, matching the two coordinates of y. It has 4 rows, so its output has four coordinates.

  3. 3
    Determine the recovered space

    The product U y is a four-coordinate vector in R4.

  4. 4
    Interpret the result

    The recovered vector has the original dimensionality, but it is an approximation because the compression used fewer dimensions.

Result

U maps the compact representation from R2 back into R4, producing an approximation of the original vector.

Best practice

When tracing a PCA transformation, track both the space and the role of each object: x is the original vector, W performs compression, y is the compact representation, U performs recovery, and x̃ is the recovered approximation.

What PCA Optimizes

The matrices W and U are not selected merely because their shapes are compatible. PCA looks for the pair that makes recovered vectors close to the original vectors across the dataset. If the dataset contains vectors x1 through xm, each vector is compressed and recovered as x̃i = U W xi. PCA chooses W and U to minimize the total squared distance between each original vector xi and its recovered version x̃i.

Definition

PCA's reconstruction objective is to minimize the total squared distance between the original dataset vectors and the vectors recovered after compression and recovery.

Datasetx1 through xmWcompressionUrecoveryRecovered vectorsx̃1 through x̃mSquared distanceoriginal versus recoveredMinimumreconstruction errorapplythenproducecompare originalscompare recoveriesminimize total
How does PCA choose the transformations that minimize the squared distance between each original vector and its recovered approximation?

The objective connects both transformations. W controls the move into the smaller space, U maps the compact representation back into the original space, and the squared distance evaluates the combined result. A pair of matrices is useful in PCA only when this combined process keeps the recovered vectors close to the originals across the dataset.

Common Reasoning Mistakes

  • Common mistake

    Treating compression as if it preserves the original number of coordinates.

    What it looks like

    Saying that y is still in R^d after applying W.

    Why it fails

    The compression matrix W has n rows with n smaller than d, so y = W x belongs to Rn.

    Do this instead

    Track the output dimension from the number of rows of W.

  • Common mistake

    Assuming recovery exactly restores the original vector.

    What it looks like

    Writing that x̃ is identical to x simply because both are in R^d.

    Why it fails

    The source describes x̃ as an approximation and evaluates it by its distance from x.

    Do this instead

    Use the phrase recovered approximation and compare it with the original using squared distance.

  • Common mistake

    Describing PCA as compression without an accuracy objective.

    What it looks like

    Claiming that any smaller representation is automatically a PCA representation.

    Why it fails

    PCA chooses W and U to minimize the total squared distance between original and recovered vectors.

    Do this instead

    Explain both stages: dimensionality reduction and reconstruction-error minimization.

  • Common mistake

    Checking only whether matrix dimensions are compatible.

    What it looks like

    Choosing W and U only because their products can be formed.

    Why it fails

    Compatible shapes allow the operations, but PCA selects the matrices according to how closely the recovered vectors match the originals.

    Do this instead

    Separate shape compatibility from the optimization goal.

Trace the Transformation

EASY

A vector x belongs to R5. A compression matrix W has 2 rows and 5 columns. A recovery matrix U has 5 rows and 2 columns. Identify the space of y = W x, the space of x̃ = U y, and the quantity PCA tries to minimize across a dataset.

Hints
  • For W x, use the number of rows of W to determine the output dimension.
  • For U y, use the number of rows of U to determine the output dimension.
  • The objective compares every original vector with its recovered approximation.
  1. 1
    Dimensionality reduction maps an original vector from Rd into a smaller space Rn, where n is less than d. The compression matrix W has n rows and d columns and produces y = W x. The recovery matrix U has d rows and n columns and produces the approximation x̃ = U y in Rd. PCA chooses W and U by minimizing the total squared distance between original vectors and their recovered approximations.

Key Takeaways

  • Dimensionality reduction is a linear mapping from Rd to Rn, with n smaller than d.
  • The compression matrix W produces the compact representation y = W x.
  • The recovery matrix U maps y back into Rd as an approximation x̃ = U y.
  • PCA selects W and U to minimize the total squared distance between original and recovered dataset vectors.
  • A recovered vector can have the original number of coordinates without restoring every original detail.

Related Topics

Related concepts

More concepts starting with L