Efficient numerical methods to solve sparse linear equations with application to PageRank

Optimization Methods and Software. 2022. Vol. 37. No. 3. P. 907–935.

Anikin A., Gasnikov A., Gornov A., Kamzolov D., Maximov Y., Nesterov Y.

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. 

Keywords: Optimization problem, PageRank, randomization, sparsity, Frank-Wolfe method