On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation

By Nicolas Gillis, Stephen A. Vavasis. 2015

86 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “Without making any assumptions, those non-convex problems are intractable (Arora et al., 2012a; Gillis & Vavasis, 2015; Song et al., 2017a; Gillis & Glineur, 2011; Razen-shteyn et al., 2016; Sontag & Roy, 2011; Hardt & Moitra, 2013; Arora et al., 2012b; Yi et al., 2014).”
Low rank approximation with entrywise l1-norm error (2017, methodology): “Indeed, the question of obtaining better algorithms was posed in Section 6 of [46], in [38], and as the second part of open question 2 in [90], among other places.”