5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ There is the 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$ Mar 6, 2015 at 13:24
  • $\begingroup$ There are a number of details that are needed to answer such a question well. First, is $A$ sparse or dense? Second, how much smaller is $k$ vs $m$? Finally, what will you be using the truncated SVD for? $\endgroup$
    – Victor Liu
    Mar 6, 2015 at 21:11

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.