A Fast Implementation of Singular Value Thresholding Algorithm using Recycling Rank Revealing Randomized Singular Value Decomposition
This work addresses the computational bottleneck of partial SVD in SVT for matrix completion, offering a faster approximation for practitioners, though it is an incremental improvement over existing randomized SVD methods.
The paper presents a fast implementation of the Singular Value Thresholding (SVT) algorithm for matrix completion by introducing a recycling rank-revealing randomized SVD (R4SVD) that reuses left singular vectors from previous iterations, reducing computational cost. The method is demonstrated on image recovery and movie recommendation, showing effectiveness for both large and small matrices.
In this paper, we present a fast implementation of the Singular Value Thresholding (SVT) algorithm for matrix completion. A rank-revealing randomized singular value decomposition (R3SVD) algorithm is used to adaptively carry out partial singular value decomposition (SVD) to fast approximate the SVT operator given a desired, fixed precision. We extend the R3SVD algorithm to a recycling rank revealing randomized singular value decomposition (R4SVD) algorithm by reusing the left singular vectors obtained from the previous iteration as the approximate basis in the current iteration, where the computational cost for partial SVD at each SVT iteration is significantly reduced. A simulated annealing style cooling mechanism is employed to adaptively adjust the low-rank approximation precision threshold as SVT progresses. Our fast SVT implementation is effective in both large and small matrices, which is demonstrated in matrix completion applications including image recovery and movie recommendation system.