Journal
APPLIED MATHEMATICS AND COMPUTATION
Volume 255, Issue -, Pages 58-65Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.amc.2014.04.053
Keywords
Google problem; Power Method; Stochastic matrices; Global rate of convergence; Gradient methods; Strong convexity
Categories
Funding
- Grant Action de recherche concerte from the Direction de la recherche scientifique - Communaute francaise de Belgique'' [ARC 04/09-315]
- Laboratory of Structural Methods of Data Analysis in Predictive Modeling, MIPT, through the RF government Grant [ag.11.G34.31.0073]
- NSF [CMMI-1232623, CCF-1415498]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1415498] Funding Source: National Science Foundation
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1232623] Funding Source: National Science Foundation
Ask authors/readers for more resources
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. (C) 2014 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
