On the Complexity of Robust PCA and $\ell_1$-norm Low-Rank Matrix Approximation
This result clarifies computational limits for researchers in data mining and machine learning working on robust PCA and related problems, but it is incremental as it confirms an expected hardness.
The paper proves that low-rank matrix approximation with respect to the component-wise $\ell_1$-norm ($\ell_1$-LRA) is NP-hard, even in the rank-one case, by reducing it from MAX CUT, addressing a long-standing belief without prior formal proof.
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.