Conventional approaches to matrix completion are sensitive to outliers and impulsive noise. This paper develops robust and computationally efficient M-estimation based matrix completion algorithms. By appropriately arranging the observed entries, and then applying alternating minimization, the robust matrix completion problem is converted into a set of regression M-estimation problems. Making use of differ- entiable loss functions, the proposed algorithm overcomes a weakness of the lp-loss (p ≤ 1), which easily gets stuck in an inferior point. We prove that our algorithm converges to a stationary point of the nonconvex problem. Huber’s joint M-estimate of regression and scale can be used as a robust starting point for Tukey’s redescending M-estimator of re- gression based on an auxiliary scale. Numerical experiments on synthetic and real-world data demonstrate the superiority to state-of-the-art approaches.