Statistical complexity of dominant eigenvector calculation

AbstractWe show that the number of arithmetic operations required to calculate a dominant ε-eigenvector of a real symmetric or complex Hermitian n × n matrix, when averaged over any density invariant under linear transformations that preserve the Frobenius norm, is bounded above by a polynomial in the size of the matrix. In fact, a specific upper bound is given in terms of n and ε. We also describe an estimate of the distance between an arbitrary complex n × m matrix and its rank one approximation