2026-07-25T09:09:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8354 2024-03-06T10:42:02Z ddc:004 open_access

Non-Negative Sparse Regression and Column Subset Selection with L1 Error Bhaskara, Aditya Lattanzi, Silvio Sparse regression L1 error optimization Column subset selection 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Bhaskara and Silvio Lattanzi 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.7 urn:nbn:de:0030-drops-83548 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode