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

Aditya Bhaskara
ITCS 2018
Google Scholar

Abstract

We consider the problems of sparse regression and column subset selection under `1
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, 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 \ell_1 error for non-negative matrices.