Combinatorial QPs via a low-dimensional subspace sampling.

Dimitris S. Papailiopoulos, Megasthenis Asteris, Alexandros G. DimakisCISS 2014 · OpenReview

Abstract

Several large scale data processing problems can be formulated as quadratic programs subject to combinatorial constraints. We present a novel low-rank approximation framework for problems such as sparse PCA, nonnegative PCA, or finding the k-densest submatrix. Our framework comes with provable approximation guarantees, that dependent on the spectrum of the data-set matrix. Our algorithm operates by solving a number of QP instances, which are randomly sampled from a low-dimensional subspace of the input matrix.
BibTeX
@inproceedings{papailiopoulos2014combinatorial,
  author = {Dimitris S. Papailiopoulos and Megasthenis Asteris and Alexandros G. Dimakis},
  title = {{Combinatorial QPs via a low-dimensional subspace sampling.}},
  booktitle = {CISS},
  year = {2014},
  url = {https://openreview.net/forum?id=z92NqWigauP},
}

Loading related content...

Figure