Can you compute rank r factorization of a n*n matrix in time O(n^2 r)?

Question

I am wondering if you can compute the SVD/eigenvectors of a rank r matrix of size n*n in time O(n^2 r)? My understanding is that standard eigenvector computations involve bringing matrix into Hesseberg form which costs O(n^3) operations.

Thanks.

Answer 1

Check out Halko-Martinsson-Tropp

Answer 2

If the matrix is real symmetric (hermitian) then there are spectrum splitting methods that can find the spectrum in O(n r^2). I am sure that can be extended to SVD calculations also. I don't have the reference handy but if you want I can look it up.

BTW do you have an upper bound on $r$?