Power Iteration

Power iteration is an iterative algorithm designed to find the dominant eigenvector of a diagonalizable matrix. It does not compute the full eigendecomposition. The algorithm starts with a random vector b₀ and repeatedly multiplies it by the matrix A, normalizing at each step: bₖ₊₁ = A bₖ / ||A bₖ||. Under mild conditions, the sequence {bₖ} converges to the eigenvector corresponding to the eigenvalue with the largest magnitude (the dominant eigenvalue). The associated eigenvalue is estimated via the Rayleigh quotient.

The convergence rate of power iteration is linear and depends on the eigenvalue gap. Specifically, the error in the eigenvector approximation decreases proportionally to |λ₂/λ₁|ᵏ, where:

• λ₁ is the dominant eigenvalue (largest magnitude).
• λ₂ is the eigenvalue with the second-largest magnitude.
• k is the iteration number.

This means convergence is fast when the spectral gap (|λ₁| - |λ₂|) is large, and can be arbitrarily slow when the two largest eigenvalues are close in magnitude. The algorithm provides no convergence guarantees for non-diagonalizable matrices or matrices where the initial vector has no component in the direction of the dominant eigenvector.

A key advantage is its low memory footprint and simplicity. The algorithm requires only:

• Storage for the matrix A (often used as a linear operator, not stored explicitly).
• A few vectors (typically two) for the current and previous iterates.

Its core operation is a matrix-vector product (matvec), making it highly efficient for large, sparse matrices where matvecs are cheap. This contrasts with direct methods like full Singular Value Decomposition (SVD), which require O(n³) operations and full matrix storage. Power iteration forms the foundation for more advanced Krylov subspace methods like the Lanczos algorithm and Arnoldi iteration.

Power iteration is directly used to compute rank-k approximations via the orthogonal iteration (block power method) and is the conceptual core of randomized SVD. For Principal Component Analysis (PCA), applying power iteration to the covariance matrix XᵀX yields the first principal component (the eigenvector with the largest eigenvalue). Repeated application with deflation or using the block version can extract the top-k components, enabling low-rank approximation as formalized by the Eckart–Young theorem. This makes it a critical primitive in model compression techniques like low-rank factorization of neural network weight matrices.

The vanilla algorithm can suffer from numerical overflow or underflow due to repeated multiplication by large or small eigenvalues. In practice, the normalization step is essential for stability. A more robust implementation often uses the Rayleigh quotient iteration for faster, cubic convergence once an approximate eigenvector is known. For finding multiple eigenvectors, deflation techniques or orthogonalization (as in subspace iteration) are required to prevent convergence to the same dominant vector. Its performance is also sensitive to the choice of the initial vector; a random vector with a non-zero component in the direction of the dominant eigenvector is typically used.

While designed for eigenproblems, the core mechanics of iterative multiplication and normalization appear in other domains:

• PageRank Algorithm: Models the web as a graph; the rank vector is the dominant eigenvector of the modified adjacency matrix, computed via power iteration.
• Markov Chain Stationary Distribution: The steady-state distribution of an irreducible, aperiodic Markov chain is the dominant left eigenvector of the transition matrix.
• Community Detection in Networks: Used in spectral clustering to find partitions based on the eigenvectors of the graph Laplacian.
• Neural Network Analysis: Estimating the spectral norm of weight matrices for regularization (e.g., Spectral Normalization in GANs) uses power iteration.

An accelerated variant of power iteration that uses the Rayleigh quotient to provide a local quadratic convergence rate toward an eigenvalue-eigenvector pair. For a Hermitian matrix A and a non-zero vector x, the Rayleigh quotient is defined as R(A, x) = (x A x) / (x x)**. The algorithm iteratively refines an eigenvector estimate and uses the corresponding Rayleigh quotient as an eigenvalue estimate, then solves a shifted linear system. This shift dramatically improves convergence compared to the linear rate of basic power iteration, especially for symmetric matrices.

A generalization of power iteration used to find the eigenvector corresponding to the eigenvalue closest to a specified shift σ. Instead of repeatedly multiplying by A, it solves the linear system (A - σI) x_{k+1} = x_k. This effectively applies the power method to the matrix (A - σI)^-1, whose dominant eigenvector corresponds to the eigenvalue of A nearest to σ. It is the core mechanism behind Rayleigh quotient iteration and is crucial for finding interior eigenvalues, not just the dominant one.

A block generalization of power iteration designed to compute a p-dimensional invariant subspace (multiple eigenvectors) of a large, sparse matrix. Instead of a single vector, it maintains and iteratively refines an orthogonal basis for a subspace Q_k, computing Z_k = A Q_k and then re-orthogonalizing via QR decomposition to get Q_{k+1}. This method is robust for computing a few of the largest (or smallest, via shifts) eigenvalues and their corresponding eigenvectors, forming the basis for many practical eigensolvers.

A Krylov subspace method for general (non-symmetric) matrices that builds an orthonormal basis for the Krylov subspace K_m(A, v) = span{v, Av, A^2v, ..., A^{m-1}v} and projects A onto it, resulting in an upper Hessenberg matrix H_m. This projection approximates extreme eigenvalues via the Ritz values. The algorithm is a stabilized version of power iteration that prevents the iterate from collapsing into the dominant eigenvector direction too quickly, enabling the approximation of multiple eigenvalues. It is the foundation of the ARPACK software and the Implicitly Restarted Arnoldi Method (IRAM).

A highly efficient specialization of the Arnoldi iteration for real symmetric (or Hermitian) matrices. Due to symmetry, the resulting projection matrix T_m is tridiagonal, drastically reducing computational cost and storage. For an n x n symmetric matrix, after m iterations (where m << n), the extremal eigenvalues of T_m (computed via methods like QR iteration) are excellent approximations to the extremal eigenvalues of A. It is the premier method for finding a few extreme eigenvalues and eigenvectors of large, sparse symmetric matrices.

The eigenvalue with the largest absolute value (magnitude) in the spectrum of a matrix. For a diagonalizable matrix A, power iteration converges to the eigenvector associated with this eigenvalue, provided the starting vector has a non-zero component in that direction. The convergence rate is linear and depends on the ratio |λ_2 / λ_1|, where λ_1 is the dominant eigenvalue and λ_2 is the next largest in magnitude. This ratio is known as the spectral gap; a larger gap yields faster convergence. The dominant eigenvalue governs the asymptotic behavior of the linear dynamical system x_{k+1} = A x_k.