Precision-induced Adaptive Randomized Low-Rank Approximation for SVD and Matrix Inversion

Singular value decomposition (SVD) and matrix inversion are ubiquitous in scientific computing. Both tasks are computationally demanding for large scale matrices. Existing algorithms can approximatively solve these problems with a given rank, which however is unknown in practice and requires considerable cost for tuning. In this paper, we tackle the SVD and matrix inversion problems from a new angle, where the optimal rank for the approximate solution is explicitly guided by the distribution of the singular values. Under the framework, we propose a precision-induced random re-normalization procedure for the considered problems without the need of guessing a good rank. The new algorithms built upon the procedure simultaneously calculate the optimal rank for the task at a desired precision level and lead to the corresponding approximate solution with a substantially reduced computational cost. The promising performance of the new algorithms is supported by both theory and numerical examples.