Efficient numerical methods to solve sparse linear equations with application to PageRank. (4th May 2022) - Anikin, Anton; Gasnikov, Alexander; Gornov, Alexander; Kamzolov, Dmitry; Maximov, Yury; Nesterov, Yurii
Abstract : Over the last two decades, the PageRank problem has received increased interest from the academic community as an efficient tool to estimate web-page importance in information retrieval. Despite numerous developments, the design of efficient optimization algorithms for the PageRank problem is still a challenge. This paper proposes three new algorithms with a linear time complexity for solving the problem over a bounded-degree graph. The idea behind them is to set up the PageRank as a convex minimization problem over a unit simplex, and then solve it using iterative methods with small iteration complexity. Our theoretical results are supported by an extensive empirical justification using real-world and simulated data.