Fast Matrix Completion Algorithm Based on Randomized Singular Value Decomposition and its Applications

The purpose of this work is to accelerate the singular value thresholding（SVT） algorithm, which is a representative algorithm of matrix completion, while preserving the accuracy. The algorithm first normalizes the input matrix, then uses singular value decomposition（SVD） to complete the matrix. Because in each iteration step of the SVT algorithm the SVD of the data matrix is computed, the overall computational time of the SVT algorithm is significant. In this paper, based on the recent results on randomized SVD algorithms we propose an improved SVT algorithm. It utilizes the block Krylov iteration scheme for computing approximate SVD to replace the standard SVD, and is based on a technique of recycling the range subspace. As the result, the proposed algorithm reduces the runtime of SVT algorithm remarkably. Our algorithm is tested for the problems of recovering color images and estimating film ratings. And, it is compared with the SVT algorithms using the standard SVD and a fast truncated SVD, respectively. The experimental results show that the proposed techniques largely accelerate the SVT algorithm. The speedup ratio is up to 7.1 and 3.2 for the image recovery problem and the film-rating estimation problem, respectively.