Randomized Approach to Matrix Completion: Applications in Recommendation Systems 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 Selection and Low-Rank Matrix Completion to efficiently reconstruct incomplete datasets. In each step, CSMC solves a convex optimization task. We introduce two algorithms that implement CSMC, each tailored to different problem sizes. A formal analysis outlines the necessary assumptions and the probability of a correct solution. To assess the impact of matrix size, rank, and the proportion of missing entries on solution quality and computation time, we conducted experiments on synthetic data. The method was applied to two real-world problems: recommendation systems and image inpainting. Our results show that CSMC delivers solutions comparable to state-of-the-art matrix completion algorithms based on convex optimization, but with significant runtime savings. This makes CSMC especially valuable for systems that require efficient processing of large, incomplete datasets while maintaining the integrity of the derived insights.