PDF Publication Title:
Text from PDF Page: 120
100 5 ⋅ an inner-outer iteration for pagerank For any iterate, we have ∥g (j) P g ≤ ∥αβj−1Pjg(0)∥ + ∑∥ )∑β P g l=1 (5.15) (5.16) (5.17) (5.18) (5.19) (5.20) (5.21) (5.22) j−1 j (0) α−β j−1 l l (0) ∥=αβ +( β j−1 α−β βlPlg(0)∥ βl ∥g(0)∥ αβj−1 +( )∑βl ≤ αβj−1 ∥g(0)∥ + ∑ l=1 = β ⎛ α−βj−1⎞ ∥g(0)∥. We can rearrange κ j to a more meaningful form using ⎝ βl=1⎠ ≡κj j−1 1 − β j−1 ∑βl =β l=1 , β j−1 α−β l=1 1−β which, after substitution into (5.18), yields κj =αβ j−1 (α − β)(1 − βj−1) + = 1−β (α − β) + (1 − α)β j 1−β α−β . This bound is monotonically converging to 1−β and we further have κj ≤ α for j ≥ 1. From this analysis, we cannot conclude that the error in the inner iteration is monotonically decreasing. It is, however, bounded by a monotonically decreasing function. At every outer iteration then, the inner Richardson iteration decreases the error by at least α. Thus, our formulation of the inner- outer algorithm will always converge regardless of the tolerance η, so long as we always do at least one inner-iteration. A mathematically precise statement of this argument follows. Theorem 17. Given 0 < α < 1 and 0 < β < α, if an inner-iteration is solved with j steps of a Richardson method then ∥x(k+1)−x∥≤κ ∥x(k)−x∥, j j . Furthermore, if j ≥ 1 for all inner iterations, then κ j ≤ α and the inner-outer iteration always converges. This theorem places no restrictions on η and only requires that we perform at least one step of the inner iteration for each outer iteration. Algorithm 2 guarantees this property because the stopping condition is not checked until after the first iteration. Thus, that algorithm always converges on the Page- Rank problem. (α−β)+(1−α)β with κj = 1−β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 |