Eigenvectors and Eigenvalues

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.

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

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.

Mistakes with Dimensions and Roles

• Treating A = X transposed X and B = X X transposed as having the same shape.

  Changing the multiplication order changes which dimension is retained in the resulting square matrix.

  Fix: Write the shape of X before forming either product, then track the order of the factors.

• Saying that B describes feature relationships because it is built from X.

  B records pairwise relationships among examples, whereas A is formed in the feature-dimensional space.

  Fix: Associate A with features and B with examples.

• Using u itself as the eigenvector of A.

  u belongs to the example-based eigenvector problem for B. The vector that A acts on is X transposed u.

  Fix: Multiply u by X transposed, then normalize the resulting vector.

• Assuming the eigenvalue changes during the transfer.

  The scalar multiplying the carried vector is still lambda.

  Fix: Track the scalar through the derivation: the corresponding eigenvalue remains lambda.

• Choosing B merely because it looks like an alternative formula.

  The computational benefit comes specifically when the number of features greatly exceeds the number of examples.

  Fix: Compare d and m before deciding which eigenvalue problem is smaller.

Check the Route

Essential Takeaways

1. For an m by d data matrix X, A = X transposed X is d by d and operates in feature-dimensional space.
2. B = X X transposed is m by m and records pairwise relationships among examples.
3. If B u = lambda u, then A X transposed u = lambda X transposed u.
4. Normalizing X transposed u produces the corresponding eigenvector of A with eigenvalue lambda.
5. The B-based route is especially useful when the number of features greatly exceeds the number of examples.