Statistical complexity of dominant eigenvector calculation (Q1186505)

The dominant eigenvector of a matrix can be found by the power method that consists of squaring and normalizing the given matrix. The paper gives the estimate \(O(\ln(n)+\ln|\ln\epsilon|)\) on the number of repeats needed for the power method for real symmetric or complex hermitian matrices of size \(n\). In fact their dominant eigenvector can be estimated to any accuracy in less algebraic operations than a polynomial in the size of the matrix.