Title: A Fast Implementation of Singular Value Thresholding Algorithm using Recycling Rank Revealing Randomized Singular Value Decomposition,
Abstract: 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.