NP-hardness and inapproximability of sparse PCA
From MaRDI portal
Publication:2361497
Abstract: We give a reduction from {sc clique} to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.
Recommendations
- Sparse PCA on fixed-rank matrices
- Sparse approximation is provably hard under coherent dictionaries
- Data-reducing principal component analysis (PCA) is NP-hard even under the simplest interval uncertainty
- Approximation hardness for a class of sparse optimization problems
- Approximation bounds for sparse principal component analysis
Cites work
- A bound on the spectral radius of graphs
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
- Optimal solutions for sparse principal component analysis
- Sparse Approximate Solutions to Linear Systems
- Sparse principal component analysis via regularized low rank matrix approximation
- Spektren endlicher Grafen
- The varimax criterion for analytic rotation in factor analysis
Cited in
(19)- Hierarchical compressed sensing
- Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes
- Several approximation algorithms for sparse best rank-1 approximation to higher-order tensors
- A note on the hardness of sparse approximation
- Sparse PCA on fixed-rank matrices
- Data-reducing principal component analysis (PCA) is NP-hard even under the simplest interval uncertainty
- Sparse approximation is provably hard under coherent dictionaries
- Approximation hardness for a class of sparse optimization problems
- Recovering PCA and sparse PCA via hybrid-(_1,_2) sparse sampling of data elements
- scientific article; zbMATH DE number 7625166 (Why is no real title available?)
- Cutting plane generation through sparse principal component analysis
- Using \(\ell_1\)-relaxation and integer programming to obtain dual bounds for sparse PCA
- Jointly low-rank and bisparse recovery: questions and partial answers
- Solving sparse principal component analysis with global support
- Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
- A communication-efficient and privacy-aware distributed algorithm for sparse PCA
- Riemannian thresholding methods for row-sparse and low-rank matrix recovery
- Beyond symmetry: best submatrix selection for the sparse truncated SVD
- Bisparse blind deconvolution through hierarchical sparse recovery
This page was built for publication: NP-hardness and inapproximability of sparse PCA
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2361497)
