Combinatorial QPs via a low-dimensional subspace sampling.
Lists
Only you see this
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...