A Combinatorial Approach to Robust PCA
Weihao Kong Mingda Qiao Rajat Sen
We study the problem of recovering Gaussian data under adversarial
corruptions when the noises are low-rank and the corruptions are on the
coordinate level. Concretely, we assume that the Gaussian noises lie in an
unknown $k$-dimensional subspace $U \subseteq \mathbb{R}^d$, and $s$ randomly
chosen coordinates of each data point fall into the control of an adversary.
This setting models the scenario of learning from high-dimensional yet
structured data that are transmitted through a highly-noisy channel, so that
the data points are unlikely to be entirely clean.
  Our main result is an efficient algorithm that, when $ks^2 = O(d)$, recovers
every single data point up to a nearly-optimal $\ell_1$ error of $\tilde
O(ks/d)$ in expectation. At the core of our proof is a new analysis of the
well-known Basis Pursuit (BP) method for recovering a sparse signal, which is
known to succeed under additional assumptions (e.g., incoherence or the
restricted isometry property) on the underlying subspace $U$. In contrast, we
present a novel approach via studying a natural combinatorial problem and show
that, over the randomness in the support of the sparse signal, a
high-probability error bound is possible even if the subspace $U$ is arbitrary.