preprint · arXiv (Cornell University) · 2024

Algorithm xxx: Faster Randomized SVD with Dynamic Shifts

Xu Feng, Wenjian Yu, Yuyang Xie, Jie Tang

Cited by 0Open access

Abstract

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. A bound of the approximation error of the randomized SVD with the shifted power iteration is also proved.

Cite this paper

APA 7

Feng, X., Yu, W., Xie, Y., & Tang, J. (2024). Algorithm xxx: Faster Randomized SVD with Dynamic Shifts. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2404.09276

MLA 9

Feng, Xu, et al. “Algorithm xxx: Faster Randomized SVD with Dynamic Shifts.” arXiv (Cornell University), 2024, https://doi.org/10.48550/arxiv.2404.09276.

Chicago

Feng, Xu, Wenjian Yu, Yuyang Xie, and Jie Tang. 2024. “Algorithm xxx: Faster Randomized SVD with Dynamic Shifts.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2404.09276.

Harvard

Feng, X. et al. (2024) ‘Algorithm xxx: Faster Randomized SVD with Dynamic Shifts’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2404.09276.

BibTeX

@misc{feng2024algorithm,
  title = {{Algorithm xxx: Faster Randomized SVD with Dynamic Shifts}},
  author = {Feng, Xu and Yu, Wenjian and Xie, Yuyang and Tang, Jie},
  journal = {arXiv (Cornell University)},
  year = {2024},
  doi = {10.48550/arxiv.2404.09276}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.