Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness.

Matthew S. Brennan Guy Bresler

Published in: CoRR (2019)

Keyphrases

average case
worst case
worst case analysis
np hard
upper bound
sparse pca
approximation algorithms
lower bound
uniform distribution
linear programming
average case complexity
computational complexity
optimal solution
principal component analysis
special case
pairwise
vc dimension
machine learning
data sets