# Approximate Sparse Linear Regression

arXiv: https://arxiv.org/abs/1609.08739 · HTML: https://mlsanity.com/paper/1609.08739/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2016.

## Built on by (most cited first, 8 of 8)

- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)

## Abstract (arXiv)

In the Sparse Linear Regression (SLR) problem, given a d × n matrix M and a d-dimensional query q, the goal is to compute a k-sparse n-dimensional vector τ such that the error ||M τ-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(nk-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 ℝd contains d+1 points contained in a hyperplane takes Omega(nd) time). Moreover, our algorithms involve formulating and solving several geometric subproblems, which we believe to be of independent interest.