Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem

DOI10.1134/S0005117911020111zbMath1233.65032OpenAlexW2051871196MaRDI QIDQ544781

Alexander Nazin, Boris T. Polyak

Publication date: 16 June 2011

Published in: Automation and Remote Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0005117911020111

zbMATH Keywords

randomized algorithmPageRanklarge sparse stochastic matrixPerron eigenvector

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Searching and sorting (68P10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Randomized algorithms (68W20) Stochastic matrices (15B51)

Related Items

Efficient numerical methods to solve sparse linear equations with application to PageRank ⋮ A mirror descent algorithm for minimization of mean Poisson flow driven losses ⋮ Saddle point mirror descent algorithm for the robust PageRank problem ⋮ A Geometric Nonlinear Conjugate Gradient Method for Stochastic Inverse Eigenvalue Problems ⋮ A Riemannian Fletcher--Reeves Conjugate Gradient Method for Doubly Stochastic Inverse Eigenvalue Problems ⋮ Statistical Clustering of a Random Network by Extremal Properties ⋮ On efficient randomized algorithms for finding the PageRank vector ⋮ On the efficiency of a randomized mirror descent algorithm in online optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank
• Recursive aggregation of estimators by the mirror descent algorithm with averaging
• Lectures on Modern Convex Optimization
• Robust Stochastic Approximation Approach to Stochastic Programming
• Variational Analysis
• Solving variational inequalities with Stochastic Mirror-Prox algorithm