Concepts / Dimensionality Reduction

Dimensionality Reduction

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

  • 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

  1. Optionally centre the data by subtracting the mean.
  2. Form , the sum of ( is the covariance matrix).
  3. Find A's eigenvalues and the unit eigenvector u of the largest one (closed form for a symmetric 2×2 matrix).
  4. Compress each point to and recover on the principal line.
  5. 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 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.

xvector in R^d Wlinear transformationyvector in R^n applyy = W x
How does a vector in Rd move through a linear transformation into a vector in Rn when 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. The result y has fewer coordinates than x, so it is the compact representation of the original vector.

Wn rows, d columnsxR^d yR^n multipliesinput to W
How does multiplying an original vector by W produce its lower-dimensional representation?
Formula, step by step
  1. 1
    x is the original vector in Rd.
  2. 2
    W is the compression matrix with n rows and d columns.
  3. 3
    Multiplication produces y, a vector in Rn.
  4. 4
    Because n is smaller than d, y contains fewer coordinates than x.

A Symbolic Compression Trace

Worked example

Following One Vector Through W

Describe the dimensions and role of each object when a vector x in Rd is compressed using a matrix W with n rows and d columns, where n is smaller than d.

  1. 1
    Identify the input

    The original vector is x, and it belongs to Rd. It therefore has d coordinates.

  2. 2
    Inspect the matrix shape

    W has n rows and d columns. Its d columns correspond to the d coordinates of x, and its n rows determine the dimension of the result.

  3. 3
    Multiply

    The product W x is defined and produces the compact vector y.

  4. 4
    Identify the output

    The compact representation y belongs to Rn. Since n is smaller than d, it has fewer coordinates than x.

Result

The compression step maps x from Rd to y in Rn using y = W x.

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 Rd, like the original x, but it is generally an approximation rather than a claim that every detail of x has been restored exactly.

yR^n Ud rows, n columnsx_tildeR^d inputx_tilde = U y
How does the recovery matrix U transform the compressed representation back into an approximation in the original space?
Formula, step by step
x_tilde = U y
  1. 1
    y is the compact representation in Rn.
  2. 2
    U is the recovery matrix with d rows and n columns.
  3. 3
    Multiplication produces x_tilde in Rd.
  4. 4
    x_tilde is an approximation of the original vector x.

The Complete Reconstruction Pipeline

The full process has two linear transformations. First, W maps x from Rd into the smaller space Rn. Then U maps y back into Rd. 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.

xR^d WcompressionyR^n Urecoveryx_tildeR^d inputy = W xinputx_tilde = U y
What happens to a vector as it is compressed into fewer dimensions and then reconstructed into the original space?
Best practice

When tracing dimensionality reduction, write down the space of every vector. The sequence is x in Rd, y in Rn, and x_tilde in Rd. This prevents the common mistake of treating the compressed vector and the recovered vector as if they lived in the same space.

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.

Formula, step by step
  1. 1
    Begin with each original vector x_i in Rd.
  2. 2
    Compress it using W to obtain W x_i in Rn.
  3. 3
    Recover it using U to obtain x_tilde_i = U W x_i in Rd.
  4. 4
    Measure the squared distance between x_i and x_tilde_i.
  5. 5
    Choose W and U to minimize the total of these squared distances across the dataset.
x_ioriginal in R^d x_tilde_irecovered in R^d squared distancebetween x_i and x_tilde_icomparecompare
How does PCA judge the quality of compression and recovery using the squared distance between each original vector and its approximation?

Mistakes to Avoid

  • Common mistake

    Treating dimensionality reduction as an arbitrary deletion of coordinates.

    What it looks like

    Describing y as a vector formed simply by removing some entries from x.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Giving W the wrong dimensions.

    What it looks like

    Calling W a d-by-n matrix when it produces y in R^n from x in R^d.

    Why it fails

    The compression matrix has n rows and d columns.

    Do this instead

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

  • Common mistake

    Assuming recovery restores the original vector exactly.

    What it looks like

    Writing x_tilde = x as if no information could differ after compression.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Optimizing only the compression matrix.

    What it looks like

    Saying that PCA chooses W without considering U.

    Why it fails

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

    Do this instead

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

  • Common mistake

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

    What it looks like

    Calling a reconstruction successful because x_tilde_i belongs to R^d.

    Why it fails

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

    Do this instead

    Connect the dimensionality change to the reconstruction-error objective.

Check Your Understanding

MEDIUM

A vector x belongs to Rd. A compression matrix W has n rows and d columns, with n smaller than d. Explain the space containing y = W x, the role of the recovery matrix U, and the quantity PCA minimizes across a dataset.

Hints
  • Use the number of rows of W to identify the dimension of y.
  • The recovery matrix has d rows and n columns.
  • Describe the objective using the squared distance between each x_i and x_tilde_i.
  1. 1
    Dimensionality reduction maps a vector from Rd to Rn 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 Rd 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.

Key Takeaways

  • Dimensionality reduction maps vectors from Rd to the lower-dimensional space Rn, where n is smaller than d.
  • The compression matrix W produces the compact representation y = W x.
  • The recovery matrix U produces x_tilde = U y, an approximation in the original space Rd.
  • PCA chooses W and U to minimize the total squared distance between original and recovered vectors.
  • The central trade-off is fewer coordinates in the compact representation versus the reconstruction error after recovery.

Related Topics

Related concepts

More concepts starting with D