Clustering Techniques
Dimensionality reduction maps vectors from R^d to R^n using a linear transformation, where n is smaller than d.
From Many Coordinates to Fewer
Suppose each data item is represented by a vector with d features. Dimensionality reduction replaces that vector with a representation containing only n coordinates, where n is smaller than d. PCA performs this replacement with a linear transformation and then evaluates the result by asking how closely the original vector can be reconstructed.
The process has two linked transformations: W moves the vector into the smaller space, and U maps that compact representation back into the original space as an approximation.
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 gives y = W x. Because y belongs to R^n, it contains fewer coordinates than x. This is the central dimensionality-reduction step.
y = W xTracking the Compressed Representation
A vector x belongs to R^d, and W has n rows and d columns, with n smaller than d. Determine the space containing y = W x.
Identify the input: The vector x has d coordinates because it belongs to R^d.
Inspect the transformation: The matrix W has n rows and d columns. Its multiplication with x produces one output coordinate for each row of W.
Identify the result: The output y = W x therefore belongs to R^n and has fewer coordinates than x.
The compression step maps x from R^d to y in R^n.
Returning to the Original Space
Compression gives the shorter vector y, but PCA also specifies 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 x̃ = U y. This 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̃ = U y
Choosing W and U
PCA does not select W and U merely because their dimensions are compatible. For a dataset containing vectors x1 through xm, each vector is first compressed and then recovered. The recovered version of xi is x̃i = U W xi. PCA chooses the pair of matrices so that the total squared distance between the original vectors and their recovered versions is as small as possible.
x̃i = U W xiChoose W and U to minimize the total squared distance between xi and x̃i for i = 1 through m.Following One Dataset Vector
Describe the complete transformation applied to one dataset vector xi.
Compress: Apply W to xi, producing the compact vector W xi in R^n.
Recover: Apply U to the compact vector, producing U W xi in R^d.
Compare: Compare the original xi with its recovered version x̃i = U W xi using their squared distance.
Aggregate: Repeat this comparison for the dataset vectors x1 through xm and consider the total squared distance.
PCA evaluates the pair W and U by the total squared reconstruction distance across the dataset.
Common Interpretation Errors
Treating dimensionality reduction as an arbitrary change of representation.
The source definition specifies a linear mapping from R^d to R^n.
Fix:
State that y = W x and that W maps the original vector into the lower-dimensional space.Giving the compressed vector the original dimension.
W has n rows, so y belongs to R^n, where n is smaller than d.
Fix:
Track the spaces explicitly: x is in R^d and y is in R^n.Treating recovery as exact restoration by definition.
The recovered vector is described as an approximation of the original vector.
Fix:
Write x̃ = U y and describe it as a vector in R^d that is evaluated by its distance from x.Optimizing compression without considering reconstruction.
PCA chooses W and U together to minimize total squared distance between original and recovered vectors.
Fix:
Include both transformations and the reconstruction-error objective.
Check Your Understanding
What do you think happens?
If x belongs to R^d and W has n rows and d columns, where does y = W x belong?
Reveal answer
Answer: R^n
The n rows of W produce n output coordinates, so the compressed vector y belongs to R^n.
A dataset contains vectors x1 through xm in R^d. Explain, in order, how W, U, and the squared distance are used when PCA evaluates one vector xi.
Hints
- Start with the compression expression W xi.
- Use U to write the recovered vector.
- End by describing the comparison between xi and its recovered version.
| Object | Role | Space or shape |
|---|---|---|
| x | Original vector | R^d |
| W | Compression matrix | n rows and d columns |
| y = W x | Compact representation | R^n |
| U | Recovery matrix | d rows and n columns |
| x̃ = U y | Recovered approximation | R^d |
The roles and dimensions of the main PCA quantities.
Essential Takeaways
- Dimensionality reduction maps vectors linearly from R^d to R^n, with n smaller than d.
- The compression matrix W produces y = W x, the lower-dimensional representation.
- The recovery matrix U produces x̃ = U y, an approximation in the original space R^d.
- For a dataset, PCA evaluates W and U by minimizing the total squared distance between original vectors and their recovered versions.
- The complete reconstruction of xi is x̃i = U W xi.
Key Takeaways
- Dimensionality reduction uses a linear mapping to replace a vector in R^d with one in the smaller space R^n.
- W performs compression, while U performs recovery.
- The recovered vector has d coordinates but is generally an approximation of the original.
- PCA chooses W and U by minimizing total squared reconstruction distance across the dataset.