Clustering Techniques
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.
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 Rd. 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 Rn, it contains fewer coordinates than x. This is the central dimensionality-reduction step.
Tracking the Compressed Representation
A vector x belongs to Rd, and W has n rows and d columns, with n smaller than d. Determine the space containing y = W x.
- 1Identify the input
The vector x has d coordinates because it belongs to Rd.
- 2Inspect the transformation
The matrix W has n rows and d columns. Its multiplication with x produces one output coordinate for each row of W.
- 3Identify the result
The output y = W x therefore belongs to Rn and has fewer coordinates than x.
The compression step maps x from Rd to y in Rn.
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.
- 1Begin with the compressed representation y in Rn.
- 2Multiply y by the recovery matrix U.
- 3Because U has d rows, the result x̃ belongs to Rd.
- 4Treat x̃ as the recovered approximation of the original vector x.
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.
Following One Dataset Vector
Describe the complete transformation applied to one dataset vector xi.
- 1Compress
Apply W to xi, producing the compact vector W xi in Rn.
- 2Recover
Apply U to the compact vector, producing U W xi in Rd.
- 3Compare
Compare the original xi with its recovered version x̃i = U W xi using their squared distance.
- 4Aggregate
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
Common mistake Treating dimensionality reduction as an arbitrary change of representation.
What it looks likeDescribing the shorter vector without identifying the linear transformation W.
Why it failsThe source definition specifies a linear mapping from Rd to Rn.
Do this insteadState that y = W x and that W maps the original vector into the lower-dimensional space.
Common mistake Giving the compressed vector the original dimension.
What it looks likeWriting that y = W x belongs to R^d.
Why it failsW has n rows, so y belongs to Rn, where n is smaller than d.
Do this insteadTrack the spaces explicitly: x is in R^d and y is in R^n.
Common mistake Treating recovery as exact restoration by definition.
What it looks likeClaiming that x̃ = U y must equal x.
Why it failsThe recovered vector is described as an approximation of the original vector.
Do this insteadWrite x̃ = U y and describe it as a vector in R^d that is evaluated by its distance from x.
Common mistake Optimizing compression without considering reconstruction.
What it looks likeSaying that PCA chooses W only to make y short.
Why it failsPCA chooses W and U together to minimize total squared distance between original and recovered vectors.
Do this insteadInclude both transformations and the reconstruction-error objective.
Check Your Understanding
What do you think happens?
If x belongs to Rd and W has n rows and d columns, where does y = W x belong?
Reveal answer
Rn
The n rows of W produce n output coordinates, so the compressed vector y belongs to Rn.
A dataset contains vectors x1 through xm in Rd. 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 | Rd |
| W | Compression matrix | n rows and d columns |
| y = W x | Compact representation | Rn |
| U | Recovery matrix | d rows and n columns |
| x̃ = U y | Recovered approximation | Rd |
The roles and dimensions of the main PCA quantities.
Essential Takeaways
- 1Dimensionality reduction maps vectors linearly from Rd to Rn, with n smaller than d.
- 2The compression matrix W produces y = W x, the lower-dimensional representation.
- 3The recovery matrix U produces x̃ = U y, an approximation in the original space Rd.
- 4For a dataset, PCA evaluates W and U by minimizing the total squared distance between original vectors and their recovered versions.
- 5The complete reconstruction of xi is x̃i = U W xi.
At a glance
- Dimensionality reduction uses a linear mapping to replace a vector in Rd with one in the smaller space Rn.
- 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.