2026-08-05T20:36:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12267 2024-03-06T10:49:29Z ddc:004 open_access

Sparse Regression via Range Counting Cardinal, Jean Ooms, Aurélien Sparse Linear Regression Orthogonal Range Searching Affine Degeneracy Testing Nearest Neighbors Hyperplane Arrangements The sparse regression problem, also known as best subset selection problem, can be cast as follows: Given a set S of n points in ℝ^d, a point y∈ ℝ^d, and an integer 2 ≤ k ≤ d, find an affine combination of at most k points of S that is nearest to y. We describe a O(n^{k-1} log^{d-k+2} n)-time randomized (1+ε)-approximation algorithm for this problem with d and ε constant. This is the first algorithm for this problem running in time o(n^k). Its running time is similar to the query time of a data structure recently proposed by Har-Peled, Indyk, and Mahabadi (ICALP'18), while not requiring any preprocessing. Up to polylogarithmic factors, it matches a conditional lower bound relying on a conjecture about affine degeneracy testing. In the special case where k = d = O(1), we provide a simple O_δ(n^{d-1+δ})-time deterministic exact algorithm, for any δ > 0. Finally, we show how to adapt the approximation algorithm for the sparse linear regression and sparse convex regression problems with the same running time, up to polylogarithmic factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jean Cardinal and Aurélien Ooms 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.20 urn:nbn:de:0030-drops-122677 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.20 eng https://creativecommons.org/licenses/by/3.0/legalcode