Adaptive randomized algorithm for finding eigenvector of stochastic matrix with application to PageRank

Abstract

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 novel adaptive randomized algorithm and provide an explicit upper bound for its rate of convergence O(¿(lnN/n)), where N is the dimension and n is the number of iterations. The bound looks promising because ¿(lnN) is not large even for very high dimensions. The proposed algorithm is based on the mirror-descent method for convex stochastic optimization.