The Fine-Grained Hardness of Sparse Linear Regression

Aparna Gupte, Vinod Vaikuntanathan

Sparse linear regression is the well-studied inference problem where one is given a design matrix $\mathbf{A}\in {\mathbb{R}}^{M\times N}$ and a response vector $\mathbf{b} \in \mat…