SVD and HITS Algorithm Power Iterations

As we know, computing the authority (or hub) score of HITS ranking method, means to use the following matrix equation:

$$\textbf{a}^{k}=A^T A\textbf{a}^{(k-1)}$$

and apply the power iteration method, but with significant problems: actually, AFAIK, the convergence in not guaranteed, for the matrix $A^T A$ is sometimes not irreducible (so we cannot use Perron-Frobenius theorem and the power method may converge to nonunique solutions).

Now, I'm wondering: why not apply the SVD to $A$, in order to find the dominant eigenvector(s) of $A^T A$? Do you notice any possible issue with this approach? Will the computational cost be prohibitive?

• I am not an expert in this sparse matrix comp's, but my intuition is that you are correct and a Krylov-based method for sparse svd (Matlab's svds, not svd) will yield better results than a "vanilla" power iteration. I wanted to mention it because the only answer up to now points in the opposite direction (and refers to non-sparse svd only). Apr 11, 2014 at 12:23

The method is typically applied to matrices that are so incredibly large that you cannot do things like an SVD. Note that in the SVD you would also compute the matrix whose vectors correspond to the singular values, and this matrix is full. This is not feasible unless $A$ is small, nor can it be done in a stable way.