dashSVD: a multi-thread parallel truncated SVD solver beating existing methods

What is it about?

Aiming to provide a faster and convenient truncated SVD algorithm for large sparse matrices from real applications (i.e. for computing a few of largest singular values and the corresponding singular vectors), a dynamically shifted power iteration technique is applied to improve the accuracy of the randomized SVD method. This results in a dynamic shifts based randomized SVD (dashSVD) algorithm, which also collaborates with the skills for handling sparse matrices. An accuracy-control mechanism is included in the dashSVD algorithm to approximately monitor the per vector error bound of computed singular vectors with negligible overhead. Experiments on real-world data validate that the dashSVD algorithm largely improves the accuracy of randomized SVD algorithm or attains same accuracy with fewer passes over the matrix, and provides an efficient accuracy-control mechanism to the randomized SVD computation, while demonstrating the advantages on runtime and parallel efficiency.

Featured Image

Photo by Pietro Jeng on Unsplash

Photo by Pietro Jeng on Unsplash

Why is it important?

It is a multi-thread parallel algorithm for computing the dominant singular values/vectors. It largely outperforms existing SVD algorithms like svds, PRIMME_SVDS, etc, for a not very high-accuracy scenario, in terms of runtime, memory usage and robustness. "It is highly beneficial and relevant in fields where low accuracy SVD computations are required, like machine learning applications". The codes written in C are shared at https://github.com/THU-numbda/dashSVD.