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

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...

Full description

Saved in:
Bibliographic Details
Published in:Optimization methods & software 2020-12, Vol.37 (3)
Main Authors: Anikin, Anton, Gasnikov, Alexander, Gornov, Alexander, Kamzolov, Dmitry, Maximov, Yury, Nesterov, Yurii
Format: Article
Language:English
Subjects:
computer science
Frank-Wolfe method
l1-optimization
linear equations, convex optimization, ranking
mathematics
MATHEMATICS AND COMPUTING
PageRank
randomization
sparsity
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. Here, we propose 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.
ISSN:1055-6788
1029-4937