On the Complexity of Robust PCA and ℓ1-Norm Low-Rank Matrix Approximation
From MaRDI portal
Publication:5219689
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
Factorization of matrices (15A23) Numerical methods for low-rank matrix approximation; matrix compression (65F55)
Related Items
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 1 -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
