Complexity of computing the leading singular vector for an $n\times n$ real matrix.

Question

We know that doing a full svd for an $n\times n$ real matrix is $\mathcal{O}(n^3)$. What about just computing the leading singular vector, say using the Lanczos algorithm? It's certainly better than $\mathcal{O}(n^3)$. My intuition is that it's either $\mathcal{O}(n^2)$ or $\mathcal{O}(n^2\log(n))$.

Answer 1

If your matrix is symmetric, you can do power iteration in $O(n^2)$ operations per iteration. Convergence depends on the ratio between the two leading eigenvalues.

In particular, if $\lambda^{(k)}$ is the estimated eigenvalue after $k$ iterations and the eigenvalues of your matrix are $|\lambda_1| \geq |\lambda_2| \geq \dots \geq |\lambda_n|$, then $$ |\lambda^{(k)} -\lambda_1| = O\left(\left|\frac{\lambda_2}{\lambda_1}\right|^{k}\right). $$

In general, since the left (resp. right) singular vectors are eigenvectors of $AA^T$ (resp. $A^TA$), you can find the leading ones by alternately applying $A^T$ and $A$ in the iteration.