Faster Matrix Completion Using Randomized SVD
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. For image inpainting and movie-rating estimation problems, the proposed accelerated SVT algorithm consumes 15X and 8X less CPU time than the methods using svds and lansvd respectively, without loss of accuracy.
Code (1)
Tasks
CPUImage InpaintingMatrix CompletionRecommendation SystemsSimilar Papers 제목 키워드 기반
Randomized Approach to Matrix Completion: Applications in Collaborative Filtering and Image Inpainting
We present a novel method for matrix completion, specifically designed for matrices where one dimension significantly exceeds the other. Our Columns Selected Matrix Completion (CSMC) method combines Column Subset Selecti…
Collaborative FilteringImage InpaintingLow-Rank Matrix CompletionMatrix Completion+2Efficient Model-Based Collaborative Filtering with Fast Adaptive PCA
A model-based collaborative filtering (CF) approach utilizing fast adaptive randomized singular value decomposition (SVD) is proposed for the matrix completion problem in recommender system. Firstly, a fast adaptive PCA …
Collaborative FilteringMatrix CompletionRecommendation SystemsFast Exact Matrix Completion: A Unified Optimization Framework for Matrix Completion
We formulate the problem of matrix completion with and without side information as a non-convex optimization problem. We design fastImpute based on non-convex gradient descent and show it converges to a global minimum th…
Matrix CompletionDictionary Learning for Massive Matrix Factorization
Sparse matrix factorization is a popular tool to obtain interpretable data decompositions, which are also effective to perform data completion or denoising. Its applicability to large datasets has been addressed with onl…
Collaborative FilteringDictionary LearningMatrix CompletionRecommendation SystemsThe Singular Value Decomposition, Applications and Beyond
The singular value decomposition (SVD) is not only a classical theory in matrix computation and analysis, but also is a powerful tool in machine learning and modern data analysis. In this tutorial we first study the basi…
BIG-bench Machine LearningMatrix Completion