Power iteration

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix , the algorithm will produce a number , which is the greatest (in absolute value) eigenvalue of , and a nonzero vector , the corresponding eigenvector of , such that . The algorithm is also known as the Von Mises iteration.[1]

Power iteration is a very simple algorithm, but it may converge slowly. It does not compute a matrix decomposition, and hence it can be used when is a very large sparse matrix.[clarification needed]

The method[edit]

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

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

If we assume has an eigenvalue that is strictly greater in magnitude than its other eigenvalues and the starting vector has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence converges to an eigenvector associated with the dominant eigenvalue.

Without the two assumptions above, the sequence does not necessarily converge. In this sequence,

,

where is an eigenvector associated with the dominant eigenvalue, and . The presence of the term implies that does not converge unless . Under the two assumptions listed above, the sequence defined by

converges to the dominant eigenvalue.[clarification needed]

One may compute this with the following algorithm (shown in Python with NumPy):

#!/usr/bin/python

import numpy as np


def power_iteration(A, num_simulations):
    # Ideally choose a random vector
    # To decrease the chance that our vector
    # Is orthogonal to the eigenvector
    b_k = np.random.rand(A.shape[1])

    for _ in range(num_simulations):
        # calculate the matrix-by-vector product Ab
        b_k1 = np.dot(A, b_k)

        # calculate the norm
        b_k1_norm = np.linalg.norm(b_k1)

        # re normalize the vector
        b_k = b_k1 / b_k1_norm

    return b_k

power_iteration(np.array([[0.5, 0.5], [0.2, 0.8]]), 10)

The vector to an associated eigenvector. Ideally, one should use the Rayleigh quotient in order to get the associated eigenvalue.

This algorithm is the one used to calculate such things as the Google PageRank.

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

Analysis[edit]

Let be decomposed into its Jordan canonical form: , where the first column of is an eigenvector of corresponding to the dominant eigenvalue . Since the dominant eigenvalue of is unique, the first Jordan block of is the matrix , where is the largest eigenvalue of A in magnitude. The starting vector can be written as a linear combination of the columns of V: . By assumption, has a nonzero component in the direction of the dominant eigenvalue, so .

The computationally useful recurrence relation for can be rewritten as: , where the expression: is more amenable to the following analysis.

The expression above simplifies as
as .
The limit follows from the fact that the eigenvalue of is less than 1 in magnitude, so as
It follows that:
as
Using this fact, can be written in a form that emphasizes its relationship with when k is large:
where and as
The sequence 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 may not converge, is nearly an eigenvector of A for large k.

Alternatively, if A is diagonalizable, then the following proof yields the same result
Let λ1, λ2, …, λm be the m eigenvalues (counted with multiplicity) of A and let v1, v2, …, vm be the corresponding eigenvectors. Suppose that is the dominant eigenvalue, so that for .

The initial vector can be written:

If is chosen randomly (with uniform probability), then c1 ≠ 0 with probability 1. Now,

The expression within parentheses converges to because for . On the other hand, we have

Therefore, converges to (a multiple of) the eigenvector . The convergence is geometric, with ratio

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

Applications[edit]

Although the power iteration method approximates only one eigenvalue of a matrix, it remains useful for certain computational problems. For instance, Google uses it to calculate the PageRank of documents in their search engine,[2] and Twitter uses it to show users recommendations of who to follow.[3] The power iteration method is especially suitable for sparse matrices, such as the web matrix, or as the matrix-free method that does not require storing the coefficient matrix explicitly, but can instead access a function evaluating matrix-vector products . For non-symmetric matrices that are well-conditioned the power iteration method can outperform more complex Arnoldi iteration. For symmetric matrices, the power iteration method is rarely used, since its convergence speed can be easily increased without sacrificing the small cost per iteration; see, e.g., Lanczos iteration and LOBPCG.

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 . Other algorithms look at the whole subspace generated by the vectors . This subspace is known as the Krylov subspace. It can be computed by Arnoldi iteration or Lanczos iteration.

See also[edit]

References[edit]

  1. ^ Richard von Mises and H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
  2. ^ Ipsen, Ilse, and Rebecca M. Wills (5–8 May 2005). "7th IMACS International Symposium on Iterative Methods in Scientific Computing" (PDF). Fields Institute, Toronto, Canada. 
  3. ^ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web