This paper considers the problem of matrix completion when some number of the
columns are completely and arbitrarily corrupted, potentially by a malicious
adversary. It is well-known that standard algorithms for matrix completion can
return arbitrarily poor results, if even a single column is corrupted. One
direct application comes from robust collaborative filtering. Here, some number
of users are so-called manipulators who try to skew the predictions of the
algorithm by calibrating their inputs to the system. In this paper, we develop
an efficient algorithm for this problem based on a combination of a trimming
procedure and a convex program that minimizes the nuclear norm and the
$\ell_{1,2}$ norm. Our theoretical results show that given a vanishing fraction
of observed entries, it is nevertheless possible to complete the underlying
matrix even when the number of corrupted columns grows. Significantly, our
results hold without any assumptions on the locations or values of the observed
entries of the manipulated columns. Moreover, we show by an
information-theoretic argument that our guarantees are nearly optimal in terms
of the fraction of sampled entries on the authentic columns, the fraction of
corrupted columns, and the rank of the underlying matrix. Our results therefore
sharply characterize the tradeoffs between sample, robustness and rank in
matrix completion.

本文解决了一种矩阵完成问题，特别是当某些列完全且任意被污染，通过一个修剪和凸程序的组合，最小化核范数和 l (1,2) 范数，我们的理论结果表明，即使观察到的条目比例很小，也可以完成底层矩阵，即使被污染的列的数量增加，还可以进行矩阵完成。