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?
1 Answer
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.
svds
function in Matlab which might a bit cheaper than the full SVD but it might be less accurate than calculating TSVD from the full SVD. $\endgroup$