Abstract | ||
---|---|---|
In this paper, we develop new methods for approximating dominant eigenvector of column-stochastic matrices. We analyze the Google matrix, and present an averaging scheme with linear rate of convergence in terms of 1-norm distance. For extending this convergence result onto general case, we assume existence of a positive row in the matrix. Our new numerical scheme, the Reduced Power Method (RPM), can be seen as a proper averaging of the power iterates of a reduced stochastic matrix. We analyze also the usual Power Method (PM) and obtain convenient conditions for its linear rate of convergence with respect to 1-norm. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.amc.2014.04.053 | Applied Mathematics and Computation |
Keywords | Field | DocType |
power method | Mathematical optimization,Stochastic matrix,Mathematical analysis,Iterative method,Matrix (mathematics),Markov chain,Rate of convergence,Mathematics,Google matrix,Eigenvalues and eigenvectors,Power iteration | Journal |
Volume | ISSN | Citations |
255 | 0096-3003 | 1 |
PageRank | References | Authors |
0.38 | 1 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yurii Nesterov | 1 | 1800 | 168.77 |
A. Nemirovski | 2 | 110 | 95.68 |