MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

PDF Publication Title:

MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY ( models-and-algorithms-for-pagerank-sensitivity )

Previous Page View | Next Page View | Return to Search List

Text from PDF Page: 119

The following argument summarizes the convergence theory for inexact inner iterations. First, we provide an expression for the error in the linear system during the inner iterations. Then we derive a monotonic bound on the error during the outer iterations. Let g( j) = y( j) − x be the error after the jth inner iteration. Lemma 16. In the inner-outer iteration with 0 < α < 1 and β < α, when the inner iterations are solved using a Richardson iteration, after j inner iterations, ⎛ α−βj−1 ⎞ g(j) =y(j)−x= αβj−1Pj +( )∑βlPl g(0) j≥1, where g(0) = y(0) − x = x(k) − x is the error after the kth outer iteration. ⎝ βl=1⎠ Proof. We proceed by induction. In the base case, g(1) = αPg(0) follows because one inner iteration is identical to an iteration of the power method. Consider g( j+1). First, expand g( j+1) = βPy( j) + (α − β)Px(k) + (1 − α)v − x = βPg( j) + (α − β)Pg(0) . Now apply the induction hypothesis and simplify: ⎛ α−βj−1 ⎞ g(j+1)=βP (αβj−1Pj+ )∑βlPl g(0)+(α−β)Pg(0) = = ⎝ βl=1⎠ ⎛ j−1⎞ αβjPj+1 +(α−β)P+(α−β)∑βlPl+1 g(0) ⎝ l=1⎠ ⎛α−βj⎞ αβjPj+1 +( )∑βlPl ⎝ βl=1⎠ g(0). We know that ∥g(1)∥ ≤ α ∥g(0)∥ because it’s just a step of the power method, and the above equation says the same thing. The next iterate satisfies ∥g(2)∥ = ∥αβP2g(0) + (α − β)Pg(0)∥ ≤ αβ ∥g(0)∥ + (α − β) ∥g(0)∥ = ((α − 1)β + α) ∥g(0)∥ ≤ α ∥g(0)∥ , (5.11) (5.12) (5.13) (5.14) and so we monotonically decrease a bound on the error for the first two iterations. 5.4 ⋅ convergence 99

PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

PDF Search Title:

MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY

Original File Name Searched:

gleich-pagerank-thesis.pdf

DIY 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