Power Iteration and Eigenvalue Algorithms

Extracting the dominant risk factor from a covariance matrix — the single direction that explains the most variance, the basis of PCA-driven factor models — means finding that matrix's largest eigenvalue and its associated eigenvector. Solving for eigenvalues exactly by finding roots of the characteristic polynomial is impractical for anything bigger than a small matrix. Power iteration sidesteps this entirely: repeatedly multiply a starting vector by the matrix, and it naturally rotates to line up with the matrix's single most dominant direction, with no polynomial-solving required at all.

An analogy: a compass needle in a strong magnetic field

Imagine a compass needle placed in a complicated magnetic field, but one field direction is much stronger than all the others nearby. No matter which way the needle starts pointing, it will gradually swing around and settle pointing along that strongest direction, because every other component of the field it's exposed to is comparatively weak and gets "washed out" relative to the dominant pull. Power iteration works the same way: repeatedly applying a matrix to a vector amplifies the vector's component along the matrix's dominant eigen-direction far more than its components along weaker directions, so after enough repetitions, only the dominant direction survives in any noticeable proportion.

The math, one piece at a time

Starting from any vector $v^{(0)}$ (not orthogonal to the dominant eigenvector, which is true for almost any random starting guess), power iteration repeats:

$$v^{(k+1)} = \frac{A\,v^{(k)}}{\|A\,v^{(k)}\|} .$$

In words: multiply the current vector by the matrix, then rescale it back to unit length (purely to prevent the numbers from growing or shrinking without bound — the direction is what matters, not the size). Why this converges: write $v^{(0)}$ as a combination of $A$'s eigenvectors, $v^{(0)} = c_1 e_1 + c_2 e_2 + \cdots$, ordered so $e_1$ has the largest eigenvalue $\lambda_1$ in absolute value. Applying $A$ once scales each term by its own eigenvalue: $A v^{(0)} = c_1 \lambda_1 e_1 + c_2 \lambda_2 e_2 + \cdots$. Applying $A$ again, $k$ total times, scales each term by $\lambda_i^k$:

$$A^k v^{(0)} = c_1 \lambda_1^k e_1 + c_2 \lambda_2^k e_2 + \cdots = \lambda_1^k \left(c_1 e_1 + c_2 \left(\frac{\lambda_2}{\lambda_1}\right)^k e_2 + \cdots\right) .$$

In plain English: every non-dominant term shrinks relative to the dominant one by a factor of $(\lambda_2/\lambda_1)^k$, which vanishes as $k$ grows, since $|\lambda_2/\lambda_1| < 1$ by assumption — so after normalizing, $v^{(k)}$ converges to (a unit multiple of) $e_1$, the dominant eigenvector, and the corresponding eigenvalue is recovered as $\lambda_1 \approx \frac{v^{(k)\top} A\, v^{(k)}}{v^{(k)\top}v^{(k)}}$ once the vector has converged. The convergence rate depends on the ratio $|\lambda_2/\lambda_1|$: the closer the two largest eigenvalues are to each other, the slower this washing-out effect and the more iterations needed.

Worked example 1: power iteration by hand

$A = \begin{pmatrix}4&1\\2&3\end{pmatrix}$ (true eigenvalues 5 and 2, dominant eigenvector direction $(1,1)$). Start $v^{(0)}=(1,0)$. Step 1: $Av^{(0)} = (4,2)$, normalize by dividing by $\|(4,2)\|\approx4.47$: $v^{(1)}\approx(0.894, 0.447)$. Step 2: $Av^{(1)} = (4(0.894)+1(0.447),\, 2(0.894)+3(0.447)) = (4.024, 3.129)$, normalize by $\|\cdot\|\approx5.10$: $v^{(2)}\approx(0.789, 0.613)$. Step 3: $Av^{(2)}=(4(0.789)+0.613,\, 2(0.789)+3(0.613))=(3.769,3.417)$, normalize by $\approx 5.086$: $v^{(3)}\approx(0.741,0.672)$. The ratio $v_1/v_2$ is moving from $\infty$ (step 0) toward 1, converging on the true dominant direction $(1,1)$, i.e. ratio 1, within a handful more iterations.

Worked example 2: convergence speed and eigenvalue ratio

For this same matrix, $\lambda_2/\lambda_1 = 2/5 = 0.4$, so after $k$ iterations the non-dominant contamination shrinks by roughly $0.4^k$: after 5 iterations, $0.4^5 \approx 0.01$ — already well converged. Contrast a matrix with eigenvalues 5 and 4.9 (nearly tied): $\lambda_2/\lambda_1 = 0.98$, and $0.98^5 \approx 0.90$ — after the same 5 iterations, 90% of the non-dominant component still remains.

What this means in practice

Power iteration (and its refinements, like the QR algorithm, which effectively runs power iteration on multiple directions simultaneously to extract several eigenvalues at once) is the workhorse behind PCA on covariance matrices, extracting dominant risk factors, PageRank-style network centrality, and any "find the single most important direction of a large matrix" problem where computing the full eigendecomposition would be unnecessary and expensive. It's efficient precisely because it only ever needs matrix-vector products, never a full matrix decomposition, making it viable on very large sparse matrices.