Principal Component Analysis
Matrix A uses X transposed X and has dimensions determined by the original features.
Why PCA Changes the Representation
A dataset may contain vectors with many features, even when a smaller representation can retain the important structure. Principal Component Analysis, or PCA, replaces each vector with a lower-dimensional representation using a linear transformation. It then evaluates that representation by how well the original vector can be approximately reconstructed.
Compression and Recovery Spaces
Start with one vector x in R^d. The compression matrix W has n rows and d columns, where n is smaller than d. Multiplying W by x gives y = W x, which belongs to R^n. Because y has fewer coordinates than x, this is the dimensionality-reduction step.
Compression does not by itself restore the original vector. A recovery matrix U has d rows and n columns. Multiplying U by the compact vector gives the recovered vector, written as x-tilde = U y. This recovered vector is again in R^d, but it is generally an approximation rather than an exact restoration of every detail.
Tracking the Vector Shapes
Suppose x has d coordinates and PCA uses n coordinates with n smaller than d. Track the shapes through compression and recovery.
Compression matrix: W has n rows and d columns, so W has shape n by d.
Compressed representation: Multiplying W by x produces y = W x in R^n. The representation has n coordinates.
Recovery matrix: U has d rows and n columns, so U has shape d by n.
Recovered vector: Multiplying U by y produces x-tilde = U y in R^d, the same dimensional space as x.
The mapping is R^d to R^n to R^d: x becomes y through W, and y becomes the approximation x-tilde through U.
Building the Two PCA Matrices
Assume X has one row for each example and one column for each original feature. If there are m examples and d features, X has m rows and d columns. Matrix A is formed by multiplying X transposed by X: A = X transposed X. Its dimensions are d by d, so A operates in the feature-dimensional space.
The same matrix A can be understood as combining the examples through outer products. If x_i is the column-vector form of example i, then A is the sum of the outer products x_i x_i transposed. This explains why A is associated with relationships in the feature-dimensional space.
Reverse the multiplication order and define B = X X transposed. Because X has m rows, B is m by m. Its entry in row i and column j is the inner product of x_i and x_j. Thus B records pairwise relationships among examples, while A is formed in the feature-dimensional space.
| Matrix | Construction | Dimensions | Relationships represented |
|---|---|---|---|
| A | X transposed X | d by d | Feature-dimensional space |
| B | X X transposed | m by m | Pairwise relationships among examples |
Transferring an Eigenvector
The useful connection between A and B comes from their multiplication order. Suppose u is an eigenvector of B with eigenvalue lambda. Then B u = lambda u. Since B equals X X transposed, multiply both sides on the left by X transposed. The left side becomes X transposed X X transposed u. Grouping the first two factors as A gives A X transposed u = lambda X transposed u.
B u = lambda u, where B = X X transposed
Choosing the Smaller Eigenproblem
The usual PCA construction works with the d by d matrix A. The source describes eigenvalue calculation for A as having complexity O(d cubed), in addition to O(m d squared) for constructing A. When d is much larger than m, this can be expensive because the feature dimension controls the size of A.
Matrix B is m by m, so it can be the more efficient matrix when the number of features greatly exceeds the number of examples. The workflow is to solve the eigenvector problem in the smaller example-based space and then use X transposed to carry each direction into the feature-based space associated with A.
Selecting A or B
A dataset has m examples and d features, with d much larger than m. Which matrix is the more attractive starting point for the eigenvector calculation?
Determine the dimensions: A is d by d, while B is m by m.
Compare the dimensions: Because d is much larger than m, the example-based matrix B is smaller.
Use the eigenvector relationship: Solve the eigenvector problem for B, then multiply an eigenvector by X transposed and normalize it to obtain the corresponding direction for A.
B is the efficient route in this situation because it replaces a d by d eigenproblem with an m by m eigenproblem while preserving a route to the feature-space eigenvectors.
Measuring Reconstruction Quality
PCA does not choose W and U merely because their matrix shapes are compatible. For a dataset containing x1 through xm, each vector is compressed and recovered as x-tilde-i = U W x_i. PCA chooses the pair to minimize the total squared distance between each original vector and its recovered version.
Minimize the total squared distance between x_i and x-tilde-i, where x-tilde-i = U W x_i
Common Matrix Confusions
Treating A and B as having the same dimensions.
The multiplication order determines which dimension is repeated in the resulting square matrix.
Fix:
Count the columns of X for A and the rows of X for B.Saying that B represents relationships among features.
B is built in the example-based space.
Fix:
Associate B with pairwise relationships among examples and A with the feature-dimensional space.Using X transposed u without explaining its role.
The eigenvector of B lives in the example-based space, while A operates in the feature-based space.
Fix:
State that X transposed carries the direction into the feature-based space, then normalize it.Assuming recovery always restores x exactly.
PCA uses fewer coordinates in the compressed representation, so the recovered vector is judged by its distance from the original.
Fix:
Describe recovery as approximate and connect it to the squared reconstruction-error objective.
Check Your Reasoning
A data matrix X has m rows and d columns. Explain the dimensions and roles of A = X transposed X and B = X X transposed. Then describe how an eigenvector u of B can be used to obtain an eigenvector direction for A.
Hints
- The rows of X correspond to examples and the columns correspond to features.
- For the eigenvector transfer, start from B u = lambda u and multiply by X transposed.
- Remember to mention normalization of X transposed u.
Describe the complete path for one vector x: first compression with W, then recovery with U. Include the space containing each intermediate vector and state what PCA minimizes across the dataset.
Hints
- W has n rows and d columns, with n smaller than d.
- U has d rows and n columns.
- The objective uses the total squared distance between each original vector and its recovered approximation.
Key Takeaways
- A = X transposed X is a d by d matrix associated with the feature-dimensional space.
- B = X X transposed is an m by m matrix that records pairwise relationships among examples.
- If B u = lambda u, then X transposed u is an eigenvector direction for A with the same eigenvalue after normalization.
- When d is much larger than m, solving the eigenproblem for B can be more efficient than working directly with A.
- W compresses x from R^d to y in R^n, U recovers an approximation in R^d, and PCA minimizes total squared reconstruction error.
Key Takeaways
- PCA can represent vectors in a lower-dimensional space through the linear mapping y = W x.
- The recovery mapping x-tilde = U y returns an approximation to the original dimensional space.
- Matrices A and B use the same data matrix X in opposite multiplication orders, producing feature-based and example-based spaces.
- The eigenvector relationship lets a solution from B transfer to A through X transposed and normalization.
- PCA chooses its compression and recovery mappings by minimizing total squared reconstruction error.