|
Автоматика и телемеханика, 2011, выпуск 2, страницы 131–141
(Mi at1290)
|
|
|
|
Эта публикация цитируется в 20 научных статьях (всего в 20 статьях)
Тематический выпуск
Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank
А. В. Назин, Б. Т. Поляк Институт проблем управления им. В. А. Трапезникова РАН, Москва
Аннотация:
Рассматривается задача оценивания собственного вектора, соответствующего наибольшему собственному значению стохастической матрицы. Известны многочисленные ее приложения, возникающие при ранжировании результатов поиска, согласованности действий мультиагентных систем, при управлении в сетях и анализе данных. Стандартная техника решения этой задачи сводится к степенному методу, но при дополнительной регуляризации исходной матрицы. Предлагается новый рандомизированный алгоритм и обосновывается равномерная (во всем классе стохастических матриц данной размерности) верхняя граница скорости сходимости вида $C\sqrt{\ln(N)/n}$, где $C$ – абсолютная постоянная, $N$ – размерность, а $n$ – число итераций. Эта граница представляется обнадеживающей, поскольку величина $\ln(N)$ совсем не велика для очень большой размерности. Алгоритм основан на методе зеркального спуска для задач выпуклой стохастической оптимизации. Обсуждается возможность применения метода к задаче PageRank о ранжировании страниц в Интернете.
Образец цитирования:
А. В. Назин, Б. Т. Поляк, “Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank”, Автомат. и телемех., 2011, № 2, 131–141; Autom. Remote Control, 72:2 (2011), 342–352
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at1290 https://www.mathnet.ru/rus/at/y2011/i2/p131
|
Статистика просмотров: |
Страница аннотации: | 1023 | PDF полного текста: | 283 | Список литературы: | 104 | Первая страница: | 33 |
|