2022/04/26 by Deshpande, Amit, Pratap, Rameshwar
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2204.12073
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 et al. \citeCohenMM17 gives a one-pass subset section that offers multiplicative (1+ε) approximation guarantee for the special case of ℓ2 subspace approximation. Mahabadi et 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, ∞).