PDF Publication Title:
Text from PDF Page: 148
126 5 ⋅ an inner-outer iteration for pagerank In this experiment, we do not investigate all the issues involved in using a heuristic to an NP-hard problem and focus on the performance of the inner-outer algorithm in a non-Web ranking context. Without any parameter optimization (i.e., using β = 0.5 and η = 10−2 ), the inner-outer scheme shows a significant performance advantage as demonstrated in table 5.6. Inner-Outer Power 188 mat-vec 271 mat-vec 36.2 hours 54.6 hours Table 5.6 – Inner-Outer performance for IsoRank. The inner-outer itera- tion(β = 0.5,η = 10−2)isalso faster than the power method on IsoRank with α = 0.95, τ = 10−7, and v sparse and non-uniform. The computations were done in pure Matlab and the product graph is never explicitly formed. 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 3 G= 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. ⎡⎢ 1 / 6 ⎢ 1/6 1/2 0 0 00⎤⎥ 0 0 1/3 00⎥ 8 Here, P = ⎢ 1/6 ⎢ 1/6 00⎥ ⎢ 1/6 ⎣ 1/6 1/2 0 1/3 0 1/2 0 00⎥ 0 1/2 1/3 01⎥ 000 10⎦ .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)