Approximate sparse linear regression

Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 timeO(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 a nely degenerate conjecture (i.e., deciding if n points in Rd contains d+ 1 points contained in a hyperplane takes (nd) time). Moreover, our algorithms involve formulating and solving several geometric subproblems, which we believe to be of independent interest.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
StatePublished - Jul 1 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Country/TerritoryCzech Republic


  • Approximate nearest neighbor
  • Nearest induced flat
  • Nearest subspace search
  • Sparse linear regression
  • Sparse recovery

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Approximate sparse linear regression'. Together they form a unique fingerprint.

Cite this