2026-07-22T06:26:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16392 2024-03-06T10:57:21Z ddc:004 open_access

One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation Deshpande, Amit Pratap, Rameshwar Subspace approximation streaming algorithms low-rank approximation adaptive sampling volume sampling subset selection We consider the problem of subset selection for 𝓁_p subspace approximation, that is, to efficiently find a small subset of data points such that solving the problem optimally for this subset gives a good approximation to solving the problem optimally for the original input. Previously known subset selection algorithms based on volume sampling and adaptive sampling [Deshpande and Varadarajan, 2007], for the general case of p ∈ [1, ∞), require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for 𝓁_p subspace approximation, for any p ∈ [1, ∞). Earlier subset selection algorithms that give a one-pass multiplicative (1+ε) approximation work under the special cases. Cohen et al. [Michael B. Cohen et al., 2017] gives a one-pass subset section that offers multiplicative (1+ε) approximation guarantee for the special case of 𝓁₂ subspace approximation. Mahabadi et al. [Sepideh Mahabadi et al., 2020] gives a one-pass noisy subset selection with (1+ε) approximation guarantee for 𝓁_p subspace approximation when p ∈ {1, 2}. Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any p ∈ [1, ∞). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amit Deshpande and Rameshwar Pratap 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.51 urn:nbn:de:0030-drops-163924 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.51 eng https://creativecommons.org/licenses/by/4.0/legalcode