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.


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.