TY - GEN

T1 - Approximate sparse linear regression

AU - Har-Peled, Sariel

AU - Indyk, Piotr

AU - Mahabadi, Sepideh

N1 - Funding Information:
[Work on this paper was partially supported by NSF AF awards CCF-1421231, and CCF-1217462.] 2 [This work was done while this author was at MIT.]
Funding Information:
This research was supported by NSF and Simons Foundation.
Publisher Copyright:
© 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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.

AB - 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.

KW - Approximate nearest neighbor

KW - Nearest induced flat

KW - Nearest subspace search

KW - Sparse linear regression

KW - Sparse recovery

UR - http://www.scopus.com/inward/record.url?scp=85049779240&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049779240&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2018.77

DO - 10.4230/LIPIcs.ICALP.2018.77

M3 - Conference contribution

AN - SCOPUS:85049779240

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

A2 - Kaklamanis, Christos

A2 - Marx, Daniel

A2 - Chatzigiannakis, Ioannis

A2 - Sannella, Donald

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

Y2 - 9 July 2018 through 13 July 2018

ER -