Efficient numerical methods to solve sparse linear equations with application to PageRank. (4th May 2022)

• Record Type: Journal Article
• Authors: Anikin, Anton; Gasnikov, Alexander; Gornov, Alexander; Kamzolov, Dmitry; Maximov, Yury; Nesterov, Yurii
• Is Part Of: Optimization methods and software. Volume 37:Number 3(2022)
• Page Start: 907
• Page End: 935
• Publication Date: 2022-05-04
• Subjects: PageRank -- sparsity -- randomization -- Frank-Wolfe method -- ℓ1-optimization; 90C25 -- 90C47 -- 90C60; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1858297
• Languages: English
• ISSNs: 1055-6788

Abstract

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.