Eigenvectors and Eigenvalues
Their eigenvectors are connected through multiplication by X transposed and normalization.
Two Routes Through the Same Data
PCA can be approached through two matrix products built from the same data matrix X. The usual feature-based matrix is A = X transposed X. A second route uses B = X X transposed. These products use the same matrix X, but their multiplication order gives them different dimensions and roles. The useful connection is that an eigenvector found for B can be carried into the feature-based space with X transposed.
Building A and B
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, so X has shape m by d. If the ith example is represented as a column vector x_i, then the ith row of X is x_i transposed. Multiplying X transposed by X creates A, which has shape d by d. Multiplying X by X transposed creates B, which has shape m by m.
| Matrix | Definition | Shape | Role |
|---|---|---|---|
| A | X transposed X | d by d | Feature-dimensional space |
| B | X X transposed | m by m | Pairwise relationships among examples |
The matrix dimensions follow from the order of multiplication.
What Each Product Represents
Matrix A can be expanded as a sum of outer products: A combines the examples through the terms x_i x_i transposed. Because A is d by d, it is formed in the space determined by the original features. Matrix B reverses the multiplication order. Its entry in row i and column j is the inner product of x_i and x_j, so B records pairwise relationships among examples. The products are therefore connected by X, but they do not describe the same coordinates.
Carrying an Eigenvector Across
Suppose u is an eigenvector of B with eigenvalue lambda. By definition, B u = lambda u. Since B equals X X transposed, this is X X transposed u = lambda u. Multiply both sides on the left by X transposed. The left side becomes X transposed X X transposed u. Group the first two factors as A, giving A X transposed u = lambda X transposed u.
The final equation has the defining eigenvector form for A: A acts on X transposed u and returns lambda times that same vector. Therefore, after normalizing X transposed u, the result is an eigenvector of A with the same eigenvalue lambda. B supplies the eigenvector problem in example-based space, and X transposed carries the direction into the feature-based space where A operates.
A Symbolic Trace
Following One Eigenvector
Let X have m rows and d columns. Suppose u is an eigenvector of B = X X transposed with eigenvalue lambda. Trace the route to an eigenvector of A = X transposed X.
- 1Start in example space
Use the eigenvector relationship B u = lambda u. The vector u belongs to the m-dimensional space associated with B.
- 2Substitute the definition of B
Replace B with X X transposed, obtaining X X transposed u = lambda u.
- 3Multiply by X transposed
Left-multiply both sides by X transposed. The left side becomes X transposed X X transposed u.
- 4Recognize A
Group X transposed X as A. The result is A X transposed u = lambda X transposed u.
- 5Normalize the carried vector
Normalize X transposed u. The normalized vector is an eigenvector of A, and its eigenvalue is still lambda.
An eigenvector u of B produces an eigenvector of A by multiplying u by X transposed and then normalizing. The corresponding eigenvalue remains lambda.
This trace is a change of space, not a change of eigenvalue. The original eigenvector u is found in the example-based space of B. Multiplication by X transposed produces a vector in the feature-based space of A. The equation shows why that carried vector has the same eigenvalue.
Choosing the Smaller Eigenvalue Problem
The usual PCA construction forms A, a d by d matrix, and calculates its eigenvalues. The source describes the eigenvalue calculation for A as having complexity O(d cubed), with an additional O(m d squared) cost for constructing A. When the number of features d is much greater than the number of examples m, B is m by m and can provide a smaller eigenvalue problem. After solving the problem for B, the relationship above supplies the route back to the feature-based solution associated with A.
A Feature-Heavy Dataset
Suppose a dataset has many more original features than examples, so d is much greater than m. Which matrix is the smaller eigenvalue problem?
- 1Identify the dimensions
A has shape d by d, while B has shape m by m.
- 2Compare d and m
Because d is much greater than m, the m by m matrix B has the smaller dimension.
- 3Use the eigenvector relationship
Solve the eigenvector problem in the example-based space of B, then multiply the resulting eigenvector by X transposed and normalize it to obtain the corresponding feature-space eigenvector of A.
The B-based route can be more efficient when the number of features greatly exceeds the number of examples.
Mistakes with Dimensions and Roles
Common mistake Treating A = X transposed X and B = X X transposed as having the same shape.
What it looks likeIf X is m by d, A is d by d and B is m by m.
Why it failsChanging the multiplication order changes which dimension is retained in the resulting square matrix.
Do this insteadWrite the shape of X before forming either product, then track the order of the factors.
Common mistake Saying that B describes feature relationships because it is built from X.
What it looks likeB has entries formed from inner products of examples x_i and x_j.
Why it failsB records pairwise relationships among examples, whereas A is formed in the feature-dimensional space.
Do this insteadAssociate A with features and B with examples.
Common mistake Using u itself as the eigenvector of A.
What it looks likeStarting with B u = lambda u does not make u an eigenvector of A.
Why it failsu belongs to the example-based eigenvector problem for B. The vector that A acts on is X transposed u.
Do this insteadMultiply u by X transposed, then normalize the resulting vector.
Common mistake Assuming the eigenvalue changes during the transfer.
What it looks likeThe derived equation is A X transposed u = lambda X transposed u.
Why it failsThe scalar multiplying the carried vector is still lambda.
Do this insteadTrack the scalar through the derivation: the corresponding eigenvalue remains lambda.
Common mistake Choosing B merely because it looks like an alternative formula.
What it looks likeUsing B without checking whether m is smaller than d.
Why it failsThe computational benefit comes specifically when the number of features greatly exceeds the number of examples.
Do this insteadCompare d and m before deciding which eigenvalue problem is smaller.
Check the Route
Let X have 8 rows and 50 columns. Identify the shape of A = X transposed X and B = X X transposed. Then suppose u satisfies B u = lambda u. State the vector that must be normalized to obtain the corresponding eigenvector of A, and state the associated eigenvalue.
Hints
- The rows of X correspond to examples and the columns correspond to features.
- A keeps the feature dimension, while B keeps the example dimension.
- The transfer from B to A uses X transposed.
What do you think happens?
For X with 8 rows and 50 columns, which matrix creates the smaller eigenvalue problem: A or B?
Reveal answer
B, because it is 8 by 8 instead of 50 by 50
A is 50 by 50 because it uses the feature dimension, while B is 8 by 8 because it uses the number of examples. Since the number of features is much greater than the number of examples, the B-based eigenvalue problem is smaller.
Essential Takeaways
- 1For an m by d data matrix X, A = X transposed X is d by d and operates in feature-dimensional space.
- 2B = X X transposed is m by m and records pairwise relationships among examples.
- 3If B u = lambda u, then A X transposed u = lambda X transposed u.
- 4Normalizing X transposed u produces the corresponding eigenvector of A with eigenvalue lambda.
- 5The B-based route is especially useful when the number of features greatly exceeds the number of examples.
At a glance
- A uses X transposed X and has dimensions determined by the number of features.
- B uses X X transposed and has dimensions determined by the number of examples.
- An eigenvector of B can be transferred to the feature space by multiplying by X transposed and normalizing.
- The transferred vector is an eigenvector of A with the same eigenvalue.
- Using B can reduce the eigenvalue problem when the number of features is much larger than the number of examples.