One-pass additive-error subset selection for ℓp subspace approximation

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 citeDeshpandeV07, 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 textitet al. citeCohenMM17 gives a one-pass subset section that offers multiplicative (1+ε) approximation guarantee for the special case of ℓ2 subspace approximation. Mahabadi textitet al. citeMahabadiRWZ20 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, ∞).