NP-Hardness and Inapproximability of Sparse PCA

2015/02/19 by Magdon-Ismail, Malik · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1502.05675

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.

Cited by

• A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

Related

• On the Worst-Case Approximability of Sparse PCA
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to\n Strong Hardness
• Sparse Principal Component Analysis: a Least Squares approximation approach
• Computational Lower Bounds for Sparse PCA
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates