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

arXiv: https://arxiv.org/abs/1509.09236 · HTML: https://mlsanity.com/paper/1509.09236/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2015.

## Built on by (most cited first, 10 of 10)

- [Learning Green's functions associated with time-dependent partial differential equations](https://mlsanity.com/paper/2204.12789/) (2022)
- [Critical Points and Convergence Analysis of Generative Deep Linear Networks Trained with Bures-Wasserstein Loss](https://mlsanity.com/paper/2303.03027/) (2023)
- [Dual Simplex Volume Maximization for Simplex-Structured Matrix Factorization](https://mlsanity.com/paper/2403.20197/) (2024)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [Binary Matrix Factorisation and Completion via Integer Programming](https://mlsanity.com/paper/2106.13434/) (2021)
- [l1-norm regularized l1-norm best-fit lines](https://mlsanity.com/paper/2402.16712/) (2024)
- [Boolean and mathbbFp-Matrix Factorization: From Theory to Practice](https://mlsanity.com/paper/2207.11917/) (2022)
- [Bi-objective Optimization in Role Mining](https://mlsanity.com/paper/2403.16757/) (2024)
- [Nonnegative Matrix Factorization in the Component-Wise L1 Norm for Sparse Data](https://mlsanity.com/paper/2603.29715/) (2026)
- [On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization](https://mlsanity.com/paper/2607.04875/) (2026)

## Abstract (arXiv)

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 at recovering 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 the best of 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, namely, 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, which we all prove to be NP-hard.