Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
type: Item
instance of: scholarly article
title: Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
zbMATH Open document ID: 1233.65032
DOI: 10.1134/S0005117911020111
published in: Automation and Remote Control
publication date: 2011-06-16T00:00:00Z
review text: This paper gives a proof of a result, previously announced without proof by the authors [Dokl. Math. 79, No. 3, 424--427 (2009; Zbl 1176.65042)], concerning the rate of convergence of their randomized algorithm for computing a Perron eigenvector of a large sparse stochastic \(N\times N\) matrix \(A\). It bounds the expected value of \(\|Ax_n-x_n\|^2\) above by \(8[(n+1)\log (N)]^{1/2}/n\), where \(x_n\) is the \(n\)th approximation of the eigenvector. The slow growth with \(N\) is important in the PageRank application, where often \(N>10^9\).
reviewed by: Alan L. Andrew
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 15B51
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 5908352
zbMATH Keywords: PageRank
zbMATH Keywords: Perron eigenvector
zbMATH Keywords: randomized algorithm
zbMATH Keywords: large sparse stochastic matrix
author: Alexander Nazin
author: Boris T. Polyak
MaRDI profile type: Publication
cites work: Q5491464
cites work: Q2758366
cites work: The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank
cites work: Smooth minimization of non-smooth functions
cites work: Recursive aggregation of estimators by the mirror descent algorithm with averaging
cites work: Robust Stochastic Approximation Approach to Stochastic Programming
cites work: Solving variational inequalities with Stochastic Mirror-Prox algorithm
cites work: Variational Analysis
cites work: Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
full work available at URL: s0005117911020111
OpenAlex ID: W2051871196
description: scientific article; zbMATH DE number 5908352