Data Matrix Representation in PCA
Matrix A uses X transposed X and has dimensions determined by the original features.
Two Ways to Represent the Same Data
PCA can work with two matrix products built from the same data matrix X. The first product is A = X transposed X. The second is B = X X transposed. They have different dimensions and different interpretations, but their eigenvectors and eigenvalues are connected. This connection lets PCA move between feature-based and example-based representations.
The multiplication order determines which dimension the resulting matrix represents: A operates in the original feature-dimensional space, while B records relationships among examples.
Reading the Matrix Dimensions
Assume X has one row for each example and one column for each original feature. Let m be the number of examples and d be the original dimensionality, or number of features. X therefore has m rows and d columns. When X is multiplied by its transpose in the order X transposed X, the result A has d rows and d columns. Its dimensions are determined by the features. When the order is reversed, X X transposed produces B with m rows and m columns. Its dimensions are determined by the examples.
| Matrix | Construction | Dimensions | What it represents |
|---|---|---|---|
| X | Original data matrix | m × d | Examples in rows and features in columns |
| A | X transposed X | d × d | Feature-dimensional space |
| B | X X transposed | m × m | Pairwise relationships among examples |
The dimensions follow directly from the multiplication order.
A = X transposed X
B = X X transposed
Feature Space and Example Space
A useful way to avoid confusion is to ask what the rows and columns index. A uses one feature index for its rows and another feature index for its columns, so it is a feature-space matrix. B uses one example index for its rows and another example index for its columns, so it is an example-space matrix. The entries of B are inner products between pairs of examples. A instead combines the examples through the outer products x_i x_i transposed.
Tracing the Eigenvector Connection
The important relationship is not that A and B are the same matrix. They are generally different sizes and operate in different spaces. Their useful connection comes from the order of multiplication. Suppose u is an eigenvector of B with eigenvalue lambda. Then B u = lambda u. Since B is 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.
The vector X transposed u is an eigenvector direction for A, and it has the same eigenvalue lambda. To obtain the normalized eigenvector, divide X transposed u by its norm.
From u to an Eigenvector of A
Mapping an example-space eigenvector into feature space
Assume X has m rows and d columns. Let u be an eigenvector of B = X X transposed with eigenvalue lambda. Show the route for constructing the corresponding normalized eigenvector of A = X transposed X.
Start with B: Because u is an eigenvector of B, B u = lambda u.
Substitute the definition of B: Replace B with X X transposed, giving X X transposed u = lambda u.
Multiply by X transposed: Multiplying both sides on the left by X transposed gives X transposed X X transposed u = lambda X transposed u.
Group the product: Since A = X transposed X, the equation becomes A X transposed u = lambda X transposed u.
Normalize the mapped vector: The vector X transposed u is the eigenvector direction for A. Normalize it by dividing by its norm to obtain the normalized vector X transposed u divided by its norm.
The B eigenvector u is carried into the feature space by X transposed. After normalization, X transposed u divided by its norm is an eigenvector of A with eigenvalue lambda.
When B Reduces the Work
The usual PCA construction forms the d by d matrix A and calculates its eigenvalues. The source describes eigenvalue calculation for A as having complexity O(d cubed), with an additional O(m d squared) cost for constructing A. If d is much larger than m, this can be expensive because the feature dimension controls the size of A.
The alternative is to form B, which is m by m, solve the eigenvector problem in example space, and then use X transposed to carry the resulting directions into feature space. When the number of features greatly exceeds the number of examples, B is the smaller matrix. This is the situation in which the B-based route can make PCA computation more efficient.
| Situation | Matrix emphasized | Reason |
|---|---|---|
| The number of features is much greater than the number of examples | B = X X transposed | B is m by m instead of d by d |
| The feature-space route is directly manageable | A = X transposed X | A is the matrix whose eigenvectors are defined in feature space |
Common Dimension Mistakes
Treating A and B as if they had the same dimensions.
A is d by d, but B is m by m because reversing the multiplication order changes which dimension indexes the result.
Fix:
Write the dimensions of X first: m rows by d columns. Then derive A and B from the multiplication order.Calling B a feature-space matrix.
The row and column indices of B refer to examples, and each entry is the inner product of two example vectors.
Fix:
Interpret B as recording pairwise relationships among examples.Using u itself as the eigenvector of A.
u belongs to the example-based eigenvector problem, while A operates in feature space.
Fix:
Multiply u by X transposed, then normalize the resulting vector.Forgetting the normalization step.
The relationship identifies the feature-space eigenvector direction, and the source specifies normalization of that direction.
Fix:
Use X transposed u divided by its norm.Choosing B for every dataset.
The efficiency advantage described in the source applies especially when d is much greater than m.
Fix:
Compare the number of features with the number of examples before choosing the smaller matrix.
Check Your Understanding
A dataset has m examples and d features, with d much greater than m. Which matrix is likely to be smaller, A = X transposed X or B = X X transposed? If u is an eigenvector of the selected matrix B, describe the operations needed to obtain the corresponding normalized eigenvector in the feature-space matrix A.
Hints
- A has dimensions d by d, while B has dimensions m by m.
- The B-based route solves the eigenvector problem in example space.
- Map the direction with X transposed and then divide by its norm.
What do you think happens?
If X has one row per example and one column per feature, which dimension determines the size of B = X X transposed?
Reveal answer
Answer: The number of examples, m
X X transposed produces an m by m matrix because X has m rows. B therefore represents pairwise relationships among examples.
Key Takeaways
- A = X transposed X is a d by d matrix formed in the original feature-dimensional space.
- B = X X transposed is an m by m matrix whose entries describe pairwise relationships among examples.
- If B u = lambda u, then X transposed u is an eigenvector direction for A with the same eigenvalue lambda.
- Normalize X transposed u by dividing it by its norm to obtain the normalized eigenvector of A.
- When the number of features greatly exceeds the number of examples, solving the problem with B can be more efficient because B is smaller than A.
Key Takeaways
- A is built as X transposed X and represents the feature-dimensional space.
- B is built as X X transposed and represents pairwise relationships among examples.
- An eigenvector u of B maps to an eigenvector direction X transposed u of A.
- Normalization is required after the mapping from example space to feature space.
- The B-based route is especially useful when there are far more features than examples.