On the Complexity of Robust PCA and $\ell_1$-norm Low-Rank Matrix
  Approximation
  The low-rank matrix approximation problem with respect to the component-wise
$\ell_1$-norm ($\ell_1$-LRA), which is closely related to robust principal
component analysis (PCA), has become a very popular tool in data mining and
machine learning. Robust PCA aims at recovering a low-rank matrix that was
perturbed with sparse noise, with applications for example in
foreground-background video separation. Although $\ell_1$-LRA is strongly
believed to be NP-hard, there is, to the best of our knowledge, no formal proof
of this fact. In this paper, we prove that $\ell_1$-LRA is NP-hard, already in
the rank-one case, using a reduction from MAX CUT. Our derivations draw
interesting connections between $\ell_1$-LRA and several other well-known
problems, namely, robust PCA, $\ell_0$-LRA, binary matrix factorization, a
particular densest bipartite subgraph problem, the computation of the cut norm
of $\{-1,+1\}$ matrices, and the discrete basis problem, which we all prove to
be NP-hard.
