License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.7
URN: urn:nbn:de:0030-drops-83548
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8354/
Bhaskara, Aditya ;
Lattanzi, Silvio
Non-Negative Sparse Regression and Column Subset Selection with L1 Error
Abstract
We consider the problems of sparse regression and column subset selection under L1 error. For both problems, we show that in the non-negative setting it is possible to obtain tight and efficient approximations, without any additional structural assumptions (such as restricted isometry, incoherence, expansion, etc.). For sparse regression, given a matrix A and a vector b with non-negative entries, we give an efficient algorithm to output a vector x of sparsity O(k), for which |Ax - b|_1 is comparable to the smallest error possible using non-negative k-sparse x. We then use this technique to obtain our main result: an efficient algorithm for column subset selection under L1 error for non-negative matrices.
BibTeX - Entry
@InProceedings{bhaskara_et_al:LIPIcs:2018:8354,
author = {Aditya Bhaskara and Silvio Lattanzi},
title = {{Non-Negative Sparse Regression and Column Subset Selection with L1 Error}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8354},
URN = {urn:nbn:de:0030-drops-83548},
doi = {10.4230/LIPIcs.ITCS.2018.7},
annote = {Keywords: Sparse regression, L1 error optimization, Column subset selection}
}
Keywords: |
|
Sparse regression, L1 error optimization, Column subset selection |
Collection: |
|
9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
12.01.2018 |