the algorithm and computation cost for truncated SVD in rank k

Question

It seems that the time cost of truncated SVD in rank k for matrix $A\in R^{m\times m}$ is $O(m^2 k)$. Could anyone show me some algorithms to calculate truncated SVD with the above time complexity?

Answer 1

There are some standard solutions to k-truncated SVD problem, including the power iteration algorithm and Krylov subspace methods.

Also, there are lots of randomized methods (with name "sketching") to speedup this method with sacrifice of the accuracy. We refer to the paper below:

Halko N, Martinsson P G, Tropp J A. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions[J]. SIAM review, 2011, 53(2): 217-288.