Principal Component hierarchy for sparse quadratic programs

We propose a novel approximation hierarchy for cardinality-constrained, convex quadraticprograms that exploits the rank-dominating eigenvectors of the quadratic matrix. Each levelof approximation admits a min-max characterization whose objective function can be op-timized over the binary variables analytically, while preserving convexity in the...