Provable Randomized Coordinate Descent for Matrix Completion

Abstract

Low-rank matrix completion, the process of estimating a low-rank matrix from a small subset of its entries, has many applications including collaborative filtering and system identification. Many algorithms have been considered to address this problem. Coordinate descent has been previously proposed to tackle scalability both in terms of runtime and space complexity. Due to the use of regularization in the method, the method provides no convergence guarantees. Additionally, the choice of the regularization parameter can significantly affect the algorithm performance. Here, we study a regularization-free randomized coordinate descent method that uses an efficient periodic refactorization to guarantee a linear convergence rate. To support the proposed algorithm, we provide an analysis of the algorithm asymptotic convergence rate alongside a per-iteration computational complexity analysis. Using numerical experiments, we verify the correctness of our analysis and illustrate the overall computation advantage of the proposed approach.