0

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.

Open
Year
2015
ArXiv
arxiv.org/abs/1509.09236
Hosting
Abstract onlyARXIV-DEFAULT

Cite

Notes

Only stored in your browser.

Attribution

Abstract & full text
arxiv.org/abs/1509.09236ARXIV-DEFAULT
TL;DR
Semantic Scholar
Attribution policy →

Abstract

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.