The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank
Alexander V. Nazin, Boris T. Polyak · Doklady Mathematics · 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 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 upper bound for its rate of convergence which is O (ln N/n ), where N is the dimension and n is the number of iterations. The bound looks promising because ln N is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed.