Timezone: »

Median Matrix Completion: from Embarrassment to Optimality
Weidong Liu · Xiaojun Mao · Raymond K. W. Wong

Wed Jul 15 05:00 AM -- 05:45 AM & Wed Jul 15 07:00 PM -- 07:45 PM (PDT) @ Virtual #None

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.

Author Information

Weidong Liu (Shanghai Jiao Tong University)
Xiaojun Mao (Fudan University)
Raymond K. W. Wong (Texas A&M University)

More from the Same Authors