0
$\begingroup$

I am looking for an implementation that calculates a truncated singular value decomposition (SVD) of a dense NxN matrix in O(N^2 k) steps with a deterministic rather than randomized method. (Here, 0<k<=N is the number of modes retained.) The Python function sklearn.decomposition.TruncatedSVD can calculate an approximate truncated SVD in O(N^2 log k) steps, but the randomization introduces errors that I seek to avoid. Other implementations, e.g. ARPACK, do full SVD decompositions and take O(N^3) steps. According to Halko et al. (2011) [https://dx.doi.org/10.1137/090771806] algorithms for deterministic approximate SVDs exist that take O(N^2 k) steps, but I have not been able to find an implementation, in any language. Thank you.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.