PDF Publication Title:
Text from PDF Page: 134
114 5 ⋅ an inner-outer iteration for pagerank 5.6.6 Inner-Outer acceleration We now compare our inner-outer method to the power method and at- tempt to explain why it converges faster. On G= 3 25 4 16 with α = 0.99, β = 0.5, and η = 10−2, the inner-outer iteration takes 112 matrix-vector products to converge to an outer tolerance of 10−8. In con- trast, the power method takes 2,013 matrix-vector products—an incredible difference! Understanding this performance requires that we investigate where the error occurs in the space of the eigenvalues of P.8 For this small graph, the stochastic matrix P is diagonalizable with eigenvalues 1, −1, 0.83, −0.4 ± 0.28i, 0.14. In figure 5.5 we plot the projected error for a few eigenmodes in the solution, for each step of the power method and the inner-outer method. This figure shows that the power method spends most of those 2,000 iterations reducing the error in the eigenvector with eigenvalue −1. The inner-outer method dispatches with this eigenvector after 20 iterations and immediately before the switch to using only the power method. The remainder of the inner-outer iterations are consumed reducing the error in the eigenvector with eigenvalue 0.83, which is a much easier task. In table 5.7 we illustrate the fact that convergence of the inner-outer itera- tions does not seem to depend on the eigenvalues of P that are on the unit circle, but rather on the magnitude of the largest non-dominant eigenvalue. This generalizes the results of the previous experiment. The ratios in the table are the change in iterates, not the error in the solution. This makes techniques based on these numbers amenable to computations. The table suggests a strategy to apply the inner-outer iterations dynamically. For the two smallest graphs we have computed all the eigenvalues, and observe the expected convergence based on λ until the round-off error inherent in the power iteration restores the component of error in the eigenmodes on the unit circle. We could build an algorithm to watch for an increase in the ratio, or watch for when the ratio gets sufficiently close to α, and then apply additional inner-outer iteration pairs to reduce the magnitude of these eigenvalues. These experiments motivate the following conjecture. Conjecture18. Theasymptoticconvergencerateoftheinner-outeriterationis αλ2, where λ2 is the eigenvalue inside the unit circle with largest magnitude. We offer the following support for the conjecture. Consider an eigenvalue of P on the unit circle: λ = e i θ . If the outer iterations are solved exactly, then (α−β)λ we reduce the error in the associated eigenvector by 1−βλ . With β = 0.5, ⎡⎢ 1 / 6 ⎢ 1/6 1/2 0 0 0 0 1/3 1/2 0 1/3 0 1/2 0 0 1/2 1/3 000 00⎤⎥ 00⎥ 8 Here, P = ⎢ 1/6 ⎢ 1/6 0 0 ⎥ . 00⎥ ⎢ 1/6 ⎣ 1/6 01⎥ 10⎦PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |