  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 that the error $||M \tau-q||$ is minimized.
This problem is equivalent to the following geometric problem: given a set $P$
of $n$ points and a query point $q$ in $d$ dimensions, find the closest
$k$-dimensional subspace to $q$, that is spanned by a subset of $k$ points in
$P$. In this paper, we present data-structures/algorithms and conditional lower
bounds for several variants of this problem (such as finding the closest
induced $k$ dimensional flat/simplex instead of a subspace).
  In particular, we present approximation algorithms for the online variants of
the above problems with query time $\tilde O(n^{k-1})$, which are of interest
in the "low sparsity regime" where $k$ is small, e.g., $2$ or $3$. For $k=d$,
this matches, up to polylogarithmic factors, the lower bound that relies on the
affinely degenerate conjecture (i.e., deciding if $n$ points in $\mathbb{R}^d$
contains $d+1$ points contained in a hyperplane takes $\Omega(n^d)$ time).
Moreover, our algorithms involve formulating and solving several geometric
subproblems, which we believe to be of independent interest.
