Data Matrix Representation in PCA
The multiplication order determines which dimension the resulting matrix represents: A operates in the original feature-dimensional space, while B records relationships among examples.
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.
- 1X has m rows and d columns.
- 2X transposed has d rows and m columns.
- 3Multiplying X transposed by X produces a d by d matrix.
- 4A is formed in the feature-dimensional space.
- 1X has m rows and d columns.
- 2X transposed has d rows and m columns.
- 3Multiplying X by X transposed produces an m by m matrix.
- 4The entry in row i and column j of B is the inner product of example vectors x_i and x_j.
- 5B records pairwise relationships among examples.
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.
- 1Start with B
Because u is an eigenvector of B, B u = lambda u.
- 2Substitute the definition of B
Replace B with X X transposed, giving X X transposed u = lambda u.
- 3Multiply by X transposed
Multiplying both sides on the left by X transposed gives X transposed X X transposed u = lambda X transposed u.
- 4Group the product
Since A = X transposed X, the equation becomes A X transposed u = lambda X transposed u.
- 5Normalize 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 |
The B-based route is especially useful when d is much greater than m.
Common Dimension Mistakes
Common mistake Treating A and B as if they had the same dimensions.
What it looks likeAssuming both products produce a d by d matrix.
Why it failsA is d by d, but B is m by m because reversing the multiplication order changes which dimension indexes the result.
Do this insteadWrite the dimensions of X first: m rows by d columns. Then derive A and B from the multiplication order.
Common mistake Calling B a feature-space matrix.
What it looks likeDescribing an entry of B as a relationship between two features.
Why it failsThe row and column indices of B refer to examples, and each entry is the inner product of two example vectors.
Do this insteadInterpret B as recording pairwise relationships among examples.
Common mistake Using u itself as the eigenvector of A.
What it looks likeStarting with B u = lambda u and concluding that u is an eigenvector of A.
Why it failsu belongs to the example-based eigenvector problem, while A operates in feature space.
Do this insteadMultiply u by X transposed, then normalize the resulting vector.
Common mistake Forgetting the normalization step.
What it looks likeUsing X transposed u without dividing by its norm.
Why it failsThe relationship identifies the feature-space eigenvector direction, and the source specifies normalization of that direction.
Do this insteadUse X transposed u divided by its norm.
Common mistake Choosing B for every dataset.
What it looks likeUsing the B-based route without checking m and d.
Why it failsThe efficiency advantage described in the source applies especially when d is much greater than m.
Do this insteadCompare 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
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
- 1A = X transposed X is a d by d matrix formed in the original feature-dimensional space.
- 2B = X X transposed is an m by m matrix whose entries describe pairwise relationships among examples.
- 3If B u = lambda u, then X transposed u is an eigenvector direction for A with the same eigenvalue lambda.
- 4Normalize X transposed u by dividing it by its norm to obtain the normalized eigenvector of A.
- 5When 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.
At a glance
- 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.