On the Complexity of Robust PCA and ${\ell }_1$-norm Low-Rank Matrix Approximation

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.

16 pages, some typos corrected

References in corpus (1)

• Sketching as a Tool for Numerical Linear Algebra

Cited by in corpus (5)

• An Overview of Robust Subspace Recovery
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• Low-Rank Matrix Approximation in the Infinity Norm
• Dual Simplex Volume Maximization for Simplex-Structured Matrix Factorization
• An Alternating Minimization Algorithm with Trajectory for Direct Exoplanet Detection -- The AMAT Algorithm