Approximate Sparse Linear Regression

Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi

In the Sparse Linear Regression (SLR) problem, given a $d\times n$ matrix $M$ and a $d$-dimensional query $q$, the goal is to compute a $k$-sparse $n$-dimensional vector $\tau$ such…