6458

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Доклад

Название: 

Adaptive Randomized Algorithm for Finding Eigenvector of Stochastic Matrix With Application to PageRank

Наименование конференции: 

  • Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference (Shanghai, 2009)

Наименование источника: 

  • Proceedings of the Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference (Shanghai, 2009)

Город: 

  • Shanghai

Издательство: 

  • IEEE

Год издания: 

2009

Страницы: 

127-132
Аннотация
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(sqrt(ln(N/n))), where N is the dimension and n is the number of iterations. The bound looks promising because sqrt(lnN) is not large even for very high dimensions. The proposed algorithm is based on the mirrordescent method for convex stochastic optimization.

Библиографическая ссылка: 

Назин А.В., Поляк Б.Т. Adaptive Randomized Algorithm for Finding Eigenvector of Stochastic Matrix With Application to PageRank / Proceedings of the Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference (Shanghai, 2009). Shanghai: IEEE, 2009. С. 127-132.