Power Iteration

Power iteration is a simple algorithm to find the dominant eigenvalue (largest in absolute value) and its eigenvector.

Algorithm:

1. Start with random vector $\mathbf{v}_0$
2. Repeat: $\mathbf{v}_{k+1} = \frac{A\mathbf{v}_k}{\|A\mathbf{v}_k\|}$
3. $\mathbf{v}_k$ converges to the dominant eigenvector; $\lambda \approx \mathbf{v}_k^\top A\mathbf{v}_k$

Why it works: express $\mathbf{v}_0$ in the eigenbasis: $\mathbf{v}_0 = \sum c_i \mathbf{e}_i$. Then $A^k\mathbf{v}_0 = \sum c_i \lambda_i^k \mathbf{e}_i$. The largest $|\lambda_i|$ dominates as $k \to \infty$.

Convergence rate: linear, proportional to $|\lambda_2/\lambda_1|$. Converges fast when the dominant eigenvalue is well-separated.

Variants:

• Inverse iteration — apply power iteration to $A^{-1}$ to find the smallest eigenvalue
• Shifted inverse iteration — $(A - \sigma I)^{-1}$ finds eigenvalue closest to $\sigma$
• QR algorithm — finds all eigenvalues; the standard production method

Practical use: PageRank is essentially power iteration on the web graph transition matrix.

See also: Eigendecomposition, Singular Value Decomposition (SVD)