  In this paper, we consider matrix completion with absolute deviation loss and
obtain an estimator of the median matrix. Despite several appealing properties
of median, the non-smooth absolute deviation loss leads to computational
challenge for large-scale data sets which are increasingly common among matrix
completion problems. A simple solution to large-scale problems is parallel
computing. However, embarrassingly parallel fashion often leads to inefficient
estimators. Based on the idea of pseudo data, we propose a novel refinement
step, which turns such inefficient estimators into a rate (near-)optimal matrix
completion procedure. The refined estimator is an approximation of a
regularized least median estimator, and therefore not an ordinary regularized
empirical risk estimator. This leads to a non-standard analysis of asymptotic
behaviors. Empirical results are also provided to confirm the effectiveness of
the proposed method.
