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

Anton Anikin, Alexander Gasnikov, Alexander Gornov, Dmitry Kamzolov, Yury Maximov, Yurii Nesterov

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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.

Original languageEnglish
JournalOptimization Methods and Software
DOIs
Publication statusPublished - 2020
Externally publishedYes

Keywords

  • Frank-Wolfe method
  • PageRank
  • l(1)-optimization
  • randomization
  • sparsity

Fingerprint

Dive into the research topics of 'Efficient numerical methods to solve sparse linear equations with application to PageRank'. Together they form a unique fingerprint.

Cite this