Average-Case Integrality Gap for Non-Negative Principal Component Analysis.
Afonso S. BandeiraDmitriy KuniskyAlexander S. WeinPublished in: CoRR (2020)
Keyphrases
- average case
- principal component analysis
- integrality gap
- linear programming relaxation
- worst case
- uniform distribution
- lower bound
- linear program
- approximation algorithms
- agnostic learning
- arbitrarily close
- dimensionality reduction
- low dimensional
- linear programming
- valid inequalities
- dnf formulas
- feature extraction
- vc dimension
- knapsack problem
- greedy algorithm
- mixed integer programming
- np hardness
- integer programming