  We consider the problem of recovering a low-rank matrix when some of its
entries, whose locations are not known a priori, are corrupted by errors of
arbitrarily large magnitude. It has recently been shown that this problem can
be solved efficiently and effectively by a convex program named Principal
Component Pursuit (PCP), provided that the fraction of corrupted entries and
the rank of the matrix are both sufficiently small. In this paper, we extend
that result to show that the same convex program, with a slightly improved
weighting parameter, exactly recovers the low-rank matrix even if "almost all"
of its entries are arbitrarily corrupted, provided the signs of the errors are
random. We corroborate our result with simulations on randomly generated
matrices and errors.
