Today, I just read a passage by chance talking about using power method to compute eigenvector. Power method is also called vector iteration, which suddenly struck me on pagerank's computation. here is the pagerank formation:
$R^(k+1)=dWR^k+(1-d)E$
and then let's look at how to use power method to compute it. from here.
Eigenvalues can be ordered in terms of their absolute values to find the dominant or largest eigenvalue of a matrix. Thus, if two distinct hypothetical matrices have the following set of eigenvalues
- 5,8,-7: then |8|>|-7|>|5| and 8 is the dominant eigenvalue.
- 0.2,-1,1: then |1|=|-1|>|0.2| and since |1|=|-1| there is no dominant eigenvalue.
In its basic form the Power Method is applied as follows:
- Asign to the candidate matrix an arbitrary eigenvector with at least one element being nonzero.
- Compute a new eigenvector.
- Normalize the eigenvector, where the normalization scalar is taken for an initial eigenvalue.
- Multiply the original matrix by the normalized eigenvector to calculate a new eigenvector.
- Normalize this eigenvector, where the normalization scalar is taken for a new eigenvalue.
- Repeat the entire process until the absolute relative error between successive eigenvalues satisfies an arbitrary tolerance (threshold) value.
What we have done here is apply repeatedly a matrix to an arbitrarily chosen eigenvector. The result converges nicely to the largest eigenvalue of the matrix; i.e.
Equation 6: AkXi = cik*Xi
Figure 7 provides a visual representation of the iteration process obtained through the Power Method for the matrix given in Figure 3. As expected, for its largest eigenvalue the iterated vector converges to an eigenvector of relative coordinates (1, 0.20).
Figure 7. Visual representation of vector iteration.
It can be demonstrated that guessing an initial eigenvector in which its first element is 1 and all others are zero produces in the next iteration step an eigenvector with elements being the first column of the matrix. Thus, one could simply choose the first column of a matrix as an initial seed.
Whether you want to try a matrix column as an initial seed, keep in mind that the rate of convergence of the power method actually depends on the nature of the eigenvalues. For closely spaced eigenvalues, the rate of convergence can be slow. Several methods for improving the rate of convergence have been proposed (Shifted Iteration, Shifted Inverse Iteration or transformation methods).
For more information about power method, look at here.
This method is so similar to Pagerank. Actually, for pagerank, we compute a web graph's dominant eigenvector, which represents the graph. It reduces the dimension from n to 1, n is the number of web pages. So the dominant eigenvector has n elements, each represents a web page, and the value indicates the importance of that page.
