Last modified: January 24, 2024

This article is written in: 🇺🇸

Power Method

The power method is a fundamental iterative algorithm for estimating the eigenvalue of largest magnitude and its associated eigenvector for a given matrix. This technique is particularly appealing when dealing with large and sparse matrices, where direct eigenvalue computations (e.g., via the characteristic polynomial) are computationally expensive or numerically unstable. The power method capitalizes on the property that repeated multiplication by a matrix $A$ will cause any initial vector to align with the direction of the eigenvector associated with the dominant eigenvalue, assuming this eigenvalue is well-separated from the others in magnitude.

• The power method iteratively refines a vector to approximate the eigenvector associated with the dominant eigenvalue.
• It is particularly efficient for large and sparse matrices since it only requires matrix-vector multiplications.
• Convergence is ensured when the largest eigenvalue in magnitude is unique and well-separated from the next largest.
• The method starts with an initial guess vector, which is repeatedly multiplied by the matrix to approach the dominant eigenvector.
• Normalization of the vector at each step prevents numerical overflow or underflow during the iterations.
• The rate of convergence depends on the ratio between the dominant eigenvalue and the second-largest eigenvalue in magnitude.
• The power method can be extended to find multiple eigenvalues by deflating the matrix after each dominant eigenvalue is found.
• It is widely used in applications such as Google's PageRank algorithm to determine the importance of web pages.

Mathematical Formulation

Given an $n\times n$ matrix $A$ and an initial guess $x^{\left(0\right)}$, the power method iterates as follows:

I. Compute:

$$y^{\left(k\right)}=A{x}^{\left(k\right)}$$

II. Normalize:

$$x^{(k+1)}=\frac{y^{\left(k\right)}}{\parallel y^{\left(k\right)}\parallel }$$

These steps are repeated until convergence. Convergence occurs when the vector $x^{\left(k\right)}$ no longer changes significantly between iterations or equivalently, when successive eigenvalue approximations stabilize.

Inverse Power Method for the Smallest Eigenvalue

If we are interested in finding the smallest eigenvalue of $A$, we can use the inverse power method. The eigenvalues of $A^{-1}$ are the reciprocals of the eigenvalues of $A$. Thus, applying the power method to $A^{-1}$ instead of $A$ will yield the eigenvector associated with the smallest eigenvalue of $A$, and the inverse of the dominant eigenvalue of $A^{-1}$ will give us the smallest eigenvalue of $A$.

Derivation

Suppose $A$ has distinct eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ arranged so that:

$$|{\lambda }_1|>|{\lambda }_2|\ge \cdots \ge |{\lambda }_n|.$$

Let $v_1,v_2,\dots ,v_n$ be the corresponding eigenvectors forming a basis. Any initial vector $x^{\left(0\right)}$ can be written as:

$$x^{\left(0\right)}=c_1{v}_1+c_2{v}_2+\cdots +c_n{v}_n,\text{with}{c}_1\ne 0.$$

Applying $A$ repeatedly:

$$A{x}^{\left(0\right)}=c_1{\lambda }_1{v}_1+c_2{\lambda }_2{v}_2+\cdots +c_n{\lambda }_n{v}_n.$$

After $k$ iterations:

$$A^k{x}^{\left(0\right)}=c_1{\lambda }_1^k{v}_1+c_2{\lambda }_2^k{v}_2+\cdots +c_n{\lambda }_n^k{v}_n.$$

As $k\to \infty$, because $|{\lambda }_1|>|{\lambda }_j|$ for $j>1$, the terms involving ${\lambda }_j^k$ vanish in comparison to ${\lambda }_1^k$. Therefore:

$$\frac{A^k{x}^{\left(0\right)}}{\parallel A^k{x}^{\left(0\right)}\parallel }\to v_1$$

and the Rayleigh quotient $\frac{x^{\left(k\right)T}A{x}^{\left(k\right)}}{x^{\left(k\right)T}{x}^{\left(k\right)}}$ tends to ${\lambda }_1$.

Thus, the power method converges to the dominant eigenvector $v_1$ and eigenvalue ${\lambda }_1$.

Algorithm Steps

I. Initialize: Choose an initial vector $x^{\left(0\right)}$ (random or based on domain knowledge).

II. Iterative Step: For $k=0,1,2,\dots$:

• Compute $y^{\left(k\right)}=A{x}^{\left(k\right)}$.
• Normalize $x^{(k+1)}=\frac{y^{\left(k\right)}}{\parallel y^{\left(k\right)}\parallel }$.

III. Convergence Check: Stop when $\parallel x^{(k+1)}-x^{\left(k\right)}\parallel$ is sufficiently small, or when changes in the estimated eigenvalue become negligible.

IV. Eigenvalue Approximation: Once converged, estimate the dominant eigenvalue as:

$${\lambda }_{\text{max}}\approx \frac{x^{\left(k\right)T}A{x}^{\left(k\right)}}{x^{\left(k\right)T}{x}^{\left(k\right)}}.$$

Example

Consider:

$$A=\left[\begin{array}{ccc}2& 11& 3\end{array}\right],x^{\left(0\right)}=\left[\begin{array}{c}11\end{array}\right].$$

First iteration:

$$y^{\left(0\right)}=A{x}^{\left(0\right)}=\left[\begin{array}{ccc}2& 11& 3\end{array}\right]\left[\begin{array}{c}11\end{array}\right]=\left[\begin{array}{c}34\end{array}\right].$$

Normalize:

$$x^{\left(1\right)}=\frac{1}{5}\left[\begin{array}{c}34\end{array}\right]=\left[\begin{array}{c}0.60.8\end{array}\right].$$

Second iteration:

$$y^{\left(1\right)}=A{x}^{\left(1\right)}=\left[\begin{array}{ccc}2& 11& 3\end{array}\right]\left[\begin{array}{c}0.60.8\end{array}\right]=\left[\begin{array}{c}2.03.0\end{array}\right].$$

Normalize:

$$x^{\left(2\right)}=\frac{1}{\sqrt{2^2+3^2}}\left[\begin{array}{c}23\end{array}\right]=\left[\begin{array}{c}0.55470.8321\end{array}\right].$$

Repeating these steps, $x^{\left(k\right)}$ converges to the eigenvector associated with the largest eigenvalue, which in this case is approximately 3.5616. The corresponding eigenvector stabilizes around:

$$\left[\begin{array}{c}0.550.83\end{array}\right]$$

Advantages

• The algorithm is straightforward to implement, making it accessible for various applications.
• It is beneficial for large and sparse matrices since it only requires matrix-vector multiplication.
• The method maintains a low memory footprint by only storing the current vector and its transformation.

Limitations

• The power method can find only the largest eigenvalue in magnitude, not all eigenvalues.
• Convergence may be slow if the magnitudes of the first and second eigenvalues are close.
• The method requires a unique largest eigenvalue to ensure convergence to a single eigenvector.