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/
Go to the corresponding LIPIcs Volume Portal

Bhaskara, Aditya ; Lattanzi, Silvio

Non-Negative Sparse Regression and Column Subset Selection with L1 Error

pdf-format:
LIPIcs-ITCS-2018-7.pdf (0.6 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI