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

Nicolas Gillis () and Stephen A. Vavasis ()
Additional contact information
Nicolas Gillis: Department of Mathematics and Operational Research, University of Mons, 7000 Mons, Belgium
Stephen A. Vavasis: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1072-1084

Abstract: The low-rank matrix approximation problem with respect to the component-wise ℓ 1 -norm ( ℓ 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 to recover a low-rank matrix that was perturbed with sparse noise, with applications for example in foreground-background video separation. Although ℓ 1 -LRA is strongly believed to be NP-hard, there is, to our knowledge, no formal proof of this fact. In this paper, we prove that ℓ 1 -LRA is NP-hard, already in the rank-one case, using a reduction from MAX CUT. Our derivations draw interesting connections between ℓ 1 -LRA and several other well-known problems, i.e., robust PCA, ℓ 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, all of which we prove to be NP-hard.

Keywords: robust PCA; low-rank matrix approximations; binary matrix factorization; cut norm; computational complexity (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0895 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:4:p:1072-1084

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().