Google Research

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

ITCS 2018

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work