Power iteration

From Wikipedia, the free encyclopedia

In mathematics, the power iteration is an eigenvalue algorithm: given a matrix A, the algorithm will produce a number λ (the eigenvalue) and a nonzero vector v (the eigenvector), such that Av = λv.

The power iteration is a very simple algorithm. It does not compute a matrix decomposition, and hence it can be used when A is very large sparse matrix. However, it will find only one eigenvalue (the one with the greatest absolute value) and it may converge only slowly.

1 The method
2 Analysis
3 Applications
4 References
5 External links

[edit] The method

The power iteration algorithm starts with a vector b₀, which may be an approximation to the dominant eigenvector or a random vector. The method is described by the iteration

$b_{k+1} = \frac{Ab_k}{\|Ab_k\|}.$

So, at every iteration, the vector b_k is multiplied by the matrix A and normalized.

Under the assumptions:

A has an eigenvalue that is strictly greater in magnitude than its other eigenvalues
The starting vector $b 0$ has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue.

then:

A subsequence of $\left( b_{k} \right)$ converges to an eigenvector associated with the dominant eigenvalue

Note that the sequence $\left( b_{k} \right)$ does not necessarily converge. It can be shown that:
$b k = e i φ k v 1 + r k$ where: $v 1$ is an eigenvector associated with the dominant eigenvalue, and $\| r_{k} \| \rightarrow 0$ . The presence of the term $e i φ k$ implies that $\left( b_{k} \right)$ does not converge unless $e i φ k = 1$ Under the two assumptions listed above, the sequence $\left( \mu_{k} \right)$ defined by: $\mu_{k} = \frac{b_{k}^{*}Ab_{k}}{b_{k}^{*}b_{k}}$ converges to the dominant eigenvalue.

The method can also be used to calculate the spectral radius of a matrix by computing the Rayleigh quotient

$\frac{b_k^\top A b_k}{b_k^\top b_k} = \frac{b_{k+1}^\top b_k}{b_k^\top b_k}.$

[edit] Analysis

Let $A$ be decomposed into its Jordan canonical form: $A = V J V - 1$ , where the first column of $V$ is an eigenvector of $A$ corresponding to the dominant eigenvalue $λ 1$ . Since the dominant eigenvalue of $A$ is unique, the first Jordan block of $J$ is the $1 \times 1$ matrix $\begin{bmatrix} \lambda_{1} \end{bmatrix}$ , where $λ 1$ is the largest eigenvalue of A in magnitude. The starting vector $b 0$ can be written as a linear combination of the columns of V: $b_{0} = c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n}$ . By assumption, $b 0$ has a nonzero component in the direction of the dominant eigenvalue, so $c_{1} \ne 0$ .

The computationally useful recurrence relation for $b k + 1$ can be rewritten as: $b_{k+1}=\frac{Ab_{k}}{\|Ab_{k}\|}=\frac{A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}$ , where the expression: $\frac{A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}$ is more amenable to the following analysis.
$\begin{matrix} b_{k} &=& \frac{A^{k}b_{0}}{\| A^{k} b_{0} \|} \\ &=& \frac{\left( VJV^{-1} \right)^{k} b_{0}}{\|\left( VJV^{-1} \right)^{k}b_{0}\|} \\ &=& \frac{ VJ^{k}V^{-1} b_{0}}{\| V J^{k} V^{-1} b_{0}\|} \\ &=& \frac{ VJ^{k}V^{-1} \left( c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n} \right)} {\| V J^{k} V^{-1} \left( c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n} \right)\|} \\ &=& \frac{ VJ^{k}\left( c_{1}e_{1} + c_{2}e_{2} + \cdots + c_{n}e_{n} \right)} {\| V J^{k} \left( c_{1}e_{1} + c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \|} \\ &=& \left( \frac{\lambda_{1}}{|\lambda_{1}|} \right)^{k} \frac{c_{1}}{|c_{1}|} \frac{ v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right)} {\| v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \| } \end{matrix}$
The expression above simplifies as $k \rightarrow \infty$
$\left( \frac{1}{\lambda_{1}} J \right)^{k} = \begin{bmatrix} [1] & & & & \\ & \left( \frac{1}{\lambda_{1}} J_{2} \right)^{k}& & & \\ & & \ddots & \\ & & & \left( \frac{1}{\lambda_{1}} J_{m} \right)^{k} \\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & & & & \\ & 0 & & & \\ & & \ddots & \\ & & & 0 \\ \end{bmatrix}$ as $k \rightarrow \infty$ .
The limit follows from the fact that the eigenvalue of $\frac{1}{\lambda_{1}} J_{i}$ is less than in 1 in magnitude, so $\left( \frac{1}{\lambda_{1}} J_{i} \right)^{k} \rightarrow 0$ as $k \rightarrow \infty$
It follows that:
$\frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \rightarrow 0$ as $k \rightarrow \infty$
Using this fact, $b k$ can be written in a form that emphasizes its relationship with $v 1$ when k is large:
$\begin{matrix} b_{k} &=& \left( \frac{\lambda_{1}}{|\lambda_{1}|} \right)^{k} \frac{c_{1}}{|c_{1}|} \frac{ v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right)} {\| v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} \left( c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \| } &=& e^{i \phi k} \frac{c_{1}}{|c_{1}|} v_{1} + r_{k} \end{matrix}$ where $e i φ = λ 1 / | λ 1 |$ and $\| r_{k} \| \rightarrow 0$ as $k \rightarrow \infty$
The sequence $\left( b_{k} \right)$ is bounded, so it contains a convergent subsequence. Note that the eigenvector corresponding to the dominant eigenvalue is only unique up to a scalar, so although the sequence $\left(b_{k}\right)$ may not converge, $b k$ is nearly an eigenvector of A for large k.

Alternatively, if A is diagonalizable, then the following proof yields the same result
Let λ₁, λ₂, …, λ_m be the m eigenvalues (counted with multiplicity) of A and let v₁, v₂, …, v_m be the corresponding eigenvectors. Suppose that $λ 1$ is the dominant eigenvalue, so that $| λ 1 | > | λ j |$ for $j > 1$ .

The initial vector $b 0$ can be written:

$b_0 = c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{m}v_{m}.$

If $b 0$ is chosen randomly (with uniform probability), then c₁ ≠ 0 with probability 1. Now,

$\begin{matrix}A^{k}b_0 & = & c_{1}A^{k}v_{1} + c_{2}A^{k}v_{2} + \cdots + c_{m}A^{k}v_{m} \\ & = & c_{1}\lambda_{1}^{k}v_{1} + c_{2}\lambda_{2}^{k}v_{2} + \cdots + c_{m}\lambda_{m}^{k}v_{m} \\ & = & c_{1}\lambda_{1}^{k} \left( v_{1} + \frac{c_{2}}{c_{1}}\left(\frac{\lambda_{2}}{\lambda_{1}}\right)^{k}v_{2} + \cdots + \frac{c_{m}}{c_{1}}\left(\frac{\lambda_{m}}{\lambda_{1}}\right)^{k}v_{m}\right). \end{matrix}$

The expression within parentheses converges to $v 1$ because $| λ j / λ 1 | < 1$ for $j > 1$ . On the other hand, we have

$b_k = \frac{A^kb_0}{\|A^kb_0\|}.$

Therefore, $b k$ converges to (a multiple of) the eigenvector $v 1$ . The convergence is geometric, with ratio

$\left| \frac{\lambda_1}{\lambda_2} \right|,$

where $λ 2$ denotes the second dominant eigenvalue. Thus, the method converges slowly if there is an eigenvalue close in magnitude to the dominant eigenvalue.

[edit] Applications

Power iteration is not used very much because it can find only the dominant eigenvalue. Nevertheless, the algorithm is very useful in some specific situations. For instance, Google uses it to calculate the page rank of documents in their search engine. ^[1]

Some of the more advanced eigenvalue algorithms can be understood as variations of the power iteration. For instance, the inverse iteration method applies power iteration to the matrix $A - 1$ . Other algorithms look at the whole subspace generated by the vectors $b k$ . This subspace is known as the Krylov subspace. It can be computed by Arnoldi iteration or Lanczos iteration.

[edit] References

^ Ipsen, Ilse, and Rebecca M. Wills, Analysis and Computation of Google's PageRank, 7th IMACS International Symposium on Iterative Methods in Scientific Computing, Fields Institute, Toronto, Canada, 5–8 May 2005.