A two-phase rank-based Soft-Impute algorithm for low-rank matrix completion

Matrix completion aims to recover an unknown low-rank matrix from a small subset of its entries. In many applications, the rank of the unknown target matrix is known in advance. In this paper, we propose a two-phase algorithm that leverages the rank information to compute both a suitable value for the regularization parameter and a warm-start for an accelerated Soft-Impute algorithm. Properties inherited from proximal gradient algorithms are exploited to propose a parameter tuning to accelerate the method and also to establish a convergence analysis. Numerical experiments with both synthetic and real data show that the proposed algorithm can recover low-rank matrices, with high precision, faster than other well-established matrix completion algorithms.