Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank

Рассматривается задача оценивания собственного вектора, соответствующего наибольшему собственному значению стохастической матрицы. Известны многочисленные ее приложения, возникающие при ранжировании результатов поиска, согласованности действий мультиагентных систем, при управлении в сетях и анализе данных. Стандартная техника решения этой задачи сводится к степенному методу, но при дополнительной регуляризации исходной матрицы. Предлагается новый рандомизированный алгоритм и обосновывается равномерная (во всем классе стохастических матриц данной размерности) верхняя граница скорости сходимости вида $C\sqrt{\ln(N)/n}$, где $C$ – абсолютная постоянная, $N$ – размерность, а $n$ – число итераций. Эта граница представляется обнадеживающей, поскольку величина $\ln(N)$ совсем не велика для очень большой размерности. Алгоритм основан на методе зеркального спуска для задач выпуклой стохастической оптимизации. Обсуждается возможность применения метода к задаче PageRank о ранжировании страниц в Интернете.

Статья представлена к публикации членом редколлегии: А. И. Кибзун