Power Iteration
Power iteration repeatedly multiplies the matrix by a vector, v_{k+1}=Av_k/||Av_k||, converging to the eigenvector of the eigenvalue with the largest absolute value.
Purpose
To approximate the dominant eigenvalue and eigenvector efficiently, used in PageRank and PCA.
Mechanism
v converges to the principal eigenvector, and the ratio ||Av_k||/||v_k|| converges to the principal eigenvalue. Convergence speed depends on |λ_1/λ_2|. Accelerations: the Rayleigh quotient, shifted iteration, and the QR algorithm.
Use cases
- PageRank computation
- PCA approximation
- Spectral analysis