PDF Publication Title:
Text from PDF Page: 134
112 5 ⋅ an inner-outer iteration for pagerank 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. 5.5 extensions In this section, we derive a few improvements to algorithm 2. 5.5.1 An inner-outer accelerated power method After a few outer iterations, the inner iterations of algorithm 2 converge rapidly. As previously mentioned, a single inner iteration is equivalent to a single step of the power method. Thus we can incorporate the following improvement to the power method: apply the inner-outer scheme, and once the inner iterations start converging quickly, switch back to the power method. After the switch, we eliminate the need to check the stopping criterion of the inner iteration and save touching one vector of memory. The change to algorithm 2 is simple. Add a line between 8-9 to check if the inner-iteration converged in less than im iterations, and if so, switch to the power method using the current iterate as the starting vector. The modified scheme is presented in algorithm 3. The value of im is small and determines the point, in terms of inner iteration count, where we switch to the power method. If im = 1 then switching to the power method saves the (α−β)+(1−α)β with κj = 1−βPDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.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 (Standard Web Page)