Faster Matrix Completion Using Randomized SVD

Abstract--Matrix completion is a widely used technique for image inpainting and personalized recommender system, etc. In this work, we focus on accelerating the matrix completion using faster randomized singular value decomposition (rSVD). Firstly, two fast randomized algorithms (rSVD-PI and rSVD-BKI) are proposed for handling sparse matrix. They make use of an eigSVD procedure and several accelerating skills. Then, with the rSVD-BKI algorithm and a new subspace recycling technique, we accelerate the singular value thresholding (SVT) method in [1] to realize faster matrix completion. Experiments show that the proposed rSVD algorithms can be 6X faster than the basic rSVD algorithm [2] while keeping same accuracy. The problem of matrix completion, or estimating missing values in a matrix, occurs in many areas of engineering and applied science such as computer vision, pattern recognition and machine learning [1], [3], [4]. For example, in computer vision and image processing problems, recovering the missing or corrupted data can be regarded as matrix completion. A recommender system provides recommendations based on the user's preferences, which are often inferred with some ratings submitted by users. This is another scenario where the matrix completion can be applied. The matrix which we wish to complete often has low rank or approximately low rank.