A randomized algorithm for finding eigenvector of stochastic matrix with application to PageRank problem
Alexander V. Nazin, Boris T. Polyak · 2009
The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent consensus, networked control and data mining. The well known power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones; they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide an explicit upper bound for its rate of convergence O(radicInN/n) where N is the dimension and n is the number of iterations. The bound looks promising because radicInN is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization.