Some empirical advances in matrix completion

Solving the matrix completion problem via rank minimization is NP hard. Recent studies have shown that this problem can be addressed as a convex nuclear-norm minimization problem, albeit at an increase in the required number of samples. This paper proposes a non-convex optimization problem (a variant of convex nuclear-norm minimization) for the solution of matrix completion. It also develops a fast numerical algorithm to solve the optimization. This empirical study shows that significant improvement can be achieved by the proposed method compared to the previous ones. The number of required samples is also dependent on the type of sampling scheme used. This work shows that blue-noise sampling schemes yield more accurate matrix completion results compared to the popular uniform random sampling. (C) 2010 Elsevier B.V. All rights reserved.