On the complexity of robust PCA and _1-norm low-rank matrix approximation

DOI10.1287/MOOR.2017.0895MaRDI QIDQ5219689zbMATH OpenOpenAlexFDO

Authors Nicolas Gillis, Stephen A. Vavasis

Publication date 12 March 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.09236

zbMATH Keywords

binary matrix factorizationcomputational complexitycut normlow-rank matrix approximations

Mathematics Subject Classification ID

Factorization of matrices (15A23) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: The low-rank matrix approximation problem with respect to the component-wise $el{l}_1$-norm ($el{l}_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 $el{l}_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 $el{l}_1$-LRA is NP-hard, already in the rank-one case, using a reduction from MAX CUT. Our derivations draw interesting connections between $el{l}_1$-LRA and several other well-known problems, namely, robust PCA, $el{l}_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.

Recommendations

• Low rank approximation with entrywise \(\ell_1\)-norm error
• Low-rank matrix approximation with weights or missing data is NP-hard
• A PTAS for ℓ_p-Low Rank Approximation
• Efficient algorithms for robust and stable principal component pursuit problems
• Robust principal component analysis: a factorization-based approach with linear complexity

Cites work

• A pure \(L_1\)-norm principal component analysis
• Approximating the Cut-Norm via Grothendieck's Inequality
• Checking robust nonsingularity is NP-hard
• Combinatorial bounds on nonnegative rank and extended formulations
• Complexity of finding dense subgraphs
• Computing the norm ∥A∥∞,1 is NP-hard^∗
• Finding approximately rank-one submatrices with the nuclear norm and _1-norm
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• Low rank approximation with entrywise \(\ell_1\)-norm error
• Low-rank matrix approximation with weights or missing data is NP-hard
• Lower Rank Approximation of Matrices by Least Squares with Any Choice of Weights
• Minimization of ±1 matrices under line shifts
• Nuclear norm minimization for the planted clique and biclique problems
• On Finding Dense Subgraphs
• On Tensors, Sparsity, and Nonnegative Factorizations
• Optimization on a Grassmann manifold with application to system identification
• Quick approximation to matrices and applications
• Rank-Sparsity Incoherence for Matrix Decomposition
• Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise
• Robust PCA via Outlier Pursuit
• Robust principal component analysis?
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Sketching as a tool for numerical linear algebra
• Structured low-rank approximation with missing data
• The \(L_1\)-norm best-fit hyperplane problem
• Using underapproximations for sparse nonnegative matrix factorization

Cited in

(18)

• A novel robust principal component analysis algorithm of nonconvex rank approximation
• Online Schatten quasi-norm minimization for robust principal component analysis
• Low-rank matrix approximation in the infinity norm
• Background subtraction with Kronecker-basis-representation based tensor sparsity and \(l_{1,1,2}\) norm
• Nonsmooth rank-one matrix factorization landscape
• Low-rank matrix approximation with weights or missing data is NP-hard
• Low rank approximation with entrywise \(\ell_1\)-norm error
• Binary component decomposition. I: The positive-semidefinite case
• Low rank approximation of binary matrices: column subset selection and generalizations
• A PTAS for ℓ_p-Low Rank Approximation
• Low-Rank Binary Matrix Approximation in Column-Sum Norm.
• Certifying the Absence of Spurious Local Minima at Infinity
• Sufficient Conditions for Instability of the Subgradient Method with Constant Step Size
• New subset selection algorithms for low rank approximation: offline and online
• Dual simplex volume maximization for simplex-structured matrix factorization
• Simple heuristics yield provable algorithms for masked low-rank approximation
• Factorized binary polynomial optimization
• Off-diagonal symmetric nonnegative matrix factorization

This page was built for publication: On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219689)