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

DOI10.1287/moor.2017.0895zbMath1434.65054arXiv1509.09236OpenAlexW3122766110MaRDI QIDQ5219689

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

computational complexitycut normlow-rank matrix approximationsbinary matrix factorization

Mathematics Subject Classification ID

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

Related Items (9)

Off-diagonal symmetric nonnegative matrix factorization ⋮ Background subtraction with Kronecker-basis-representation based tensor sparsity and \(l_{1,1,2}\) norm ⋮ Nonsmooth rank-one matrix factorization landscape ⋮ Certifying the Absence of Spurious Local Minima at Infinity ⋮ Sufficient Conditions for Instability of the Subgradient Method with Constant Step Size ⋮ Unnamed Item ⋮ Low-Rank Binary Matrix Approximation in Column-Sum Norm. ⋮ Low-rank matrix approximation in the infinity norm ⋮ Binary Component Decomposition Part I: The Positive-Semidefinite Case

Cites Work

• Unnamed Item
• Unnamed Item
• A pure \(L_1\)-norm principal component analysis
• Optimization on a Grassmann manifold with application to system identification
• Nuclear norm minimization for the planted clique and biclique problems
• Using underapproximations for sparse nonnegative matrix factorization
• Quick approximation to matrices and applications
• Complexity of finding dense subgraphs
• Combinatorial bounds on nonnegative rank and extended formulations
• The \(L_1\)-norm best-fit hyperplane problem
• Checking robust nonsingularity is NP-hard
• Structured Low-Rank Approximation with Missing Data
• Computational Advertising: Techniques for Targeting Relevant Ads
• Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise
• Robust principal component analysis?
• Rank-Sparsity Incoherence for Matrix Decomposition
• Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard
• On Finding Dense Subgraphs
• Lower Rank Approximation of Matrices by Least Squares with Any Choice of Weights
• Computing the norm ∥A∥∞,1 is NP-hard^∗
• On Tensors, Sparsity, and Nonnegative Factorizations
• Low rank approximation with entrywise l ₁ -norm error
• Robust PCA via Outlier Pursuit
• Finding Approximately Rank-One Submatrices with the Nuclear Norm and $\ell_1$-Norm
• Approximating the Cut-Norm via Grothendieck's Inequality
• Minimization of ±1 matrices under line shifts
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

This page was built for publication: On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation