The existing matrix completion methods focus on optimizing the relaxation of rank function such as nuclear norm, Schatten-<inline-formula><tex-math notation="LaTeX">$p$</tex-math><alternatives><mml:math><mml:mi>p</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq1-3157083.gif"/></alternatives></inline-formula> norm, <italic>etc</italic>. They usually need many iterations to converge. Moreover, only the low-rank property of matrices is utilized in most existing models and several methods that incorporate other knowledge are quite time-consuming in practice. To address these issues, we propose a novel non-convex surrogate that can be optimized by closed-form solutions, such that it empirically converges within dozens of iterations. Besides, the optimization is parameter-free and the convergence is proved. Compared with the relaxation of rank, the surrogate is motivated by optimizing an upper-bound of rank. We theoretically validate that it is equivalent to the existing matrix completion models. Besides the low-rank assumption, we intend to exploit the column-wise correlation for matrix completion, and thus an adaptive correlation learning, which is scaling-invariant, is developed. More importantly, after incorporating the correlation learning, the model can be still solved by closed-form solutions such that it still converges fast. Experiments show the effectiveness of the non-convex surrogate and adaptive correlation learning.