Top eigenvector by power iteration
Hard22 min13 hidden tests
An analytics team wants the main direction of variation in a feature covariance matrix, its first principal component, without a full eigendecomposition. Power iteration finds it by multiplying a start vector by the matrix again and again, rescaling to length 1 each time. Write power_iteration(A, v0, num_iters) that runs exactly num_iters steps from v0 and returns the eigenvalue estimate and the vector. The steps, the stopping case and the sign rule are in the requirements.
Step the power iteration
v ← A v / |A v|, estimate v · A vStart: v0 scaled to length 1 is (0.71, 0.71). Press Step: A v = (2.12, 0.71), then rescale it to length 1.
Step 0. Estimate 2.
Examples
One step tilts the vector toward the first axis, where the eigenvalue is 3
power_iteration([[3, 0], [0, 1]], [1, 1], 1)
returns (2.8, [0.948683, 0.316228])
After 20 steps the estimate has settled on the top eigenvalue, 3
power_iteration([[2, 1], [1, 2]], [1, 0], 20)
returns (3, [0.707107, 0.707107])
The top eigenvalue is negative, so v flips sign each step until the sign rule fixes it
power_iteration([[-4, 0], [0, 1]], [1, 1], 3)
returns (-3.99878, [0.999878, -0.0156231])
Requirements
Ais a symmetric (d, d) list or array,v0a nonzero list or 1-D array of length d, andnum_itersan integer of 0 or more.- Scale
v0to length 1. Then repeatnum_iterstimes: w = A @ v; if w is all zeros, stop early; otherwise v = w / |w|. - The eigenvalue estimate is the Rayleigh quotient v . (A @ v) of the final v.
- Before returning, flip the sign of v if needed so that its entry with the largest absolute value is positive (the first such entry on a tie).
- Return a tuple
(eigenvalue, v): a float and a 1-D float array of length d.
The idea behind it
An eigenvector of a matrix A is a direction that A only stretches: A v = lambda v, with eigenvalue lambda. For a covariance matrix, the eigenvector with the largest eigenvalue is the first principal component, the direction in which the data varies most.
Write the start vector as a mix of eigenvectors. Each multiply by A scales every part by its own eigenvalue, so after k steps the part along the top eigenvector has grown by |lambda_1|^k and the others by smaller factors. Rescaling to length 1 after each step keeps the numbers finite. The error shrinks like |lambda_2 / lambda_1|^k, so a clear gap between the top two eigenvalues means fast convergence.
The Rayleigh quotient v . (A v) turns the current vector into an eigenvalue estimate and keeps its sign. Eigenvectors have no built-in sign, and when the top eigenvalue is negative, v flips every step. A sign rule makes the answer well defined.
Power iteration needs only matrix-vector products, so it scales to huge sparse matrices. PageRank is power iteration on the web's link matrix, and spectral normalization in neural networks uses one step per training update.