Matrix completion with capped nuclear norm via majorized proximal minimization

We investigate the problem of matrix completion with capped nuclear norm regularization. Different from most existing regularizations that minimize all the singular values simultaneously, capped nuclear norm only penalties the singular values smaller than certain threshold. Due to its non-smoothness and non-convexity, by formulating with Majorization Minimization (MM) approach, we develop a fast Majorized Proximal Minimization Impute (MPM-Impute) algorithm. At each iteration, the sub-problem is relaxed to a surrogate (upper bound) function and solved via proximal minimization with closed form solution. Though it requires singular value decompositions (SVD) at each iteration, by incorporating with the randomized algorithm, we propose the Randomized Truncated Singular Value Thresholding (RTSVT) operator to lower the computational cost. In addition, in contrast with most MM approaches, our algorithm is guaranteed to converge to the stationary points. Experimental results on synthetic data, image inpainting show that the completion results exceed or achieve comparable performance than state-of-the-art, yet several times faster.