One-pass additive-error subset selection for ${\mathrm{\ell }}_p$ subspace approximation

We consider the problem of subset selection for ${\mathrm{\ell }}_p$ subspace approximation, that is, to efficiently find a \emph{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 \cite{DeshpandeV07}, for the general case of $p \in [1, \infty)$, require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for ${\mathrm{\ell }}_p$ subspace approximation, for any $p\in [1,\mathrm{\infty })$. Earlier subset selection algorithms that give a one-pass multiplicative $(1+ϵ)$ approximation work under the special cases. Cohen $\mathit{\text{et}}\mathit{\text{al.}}$ \cite{CohenMM17} gives a one-pass subset section that offers multiplicative $(1+ϵ)$ approximation guarantee for the special case of ${\mathrm{\ell }}_2$ subspace approximation. Mahabadi $\mathit{\text{et}}\mathit{\text{al.}}$ \cite{MahabadiRWZ20} gives a one-pass \emph{noisy} subset selection with $(1+ϵ)$ approximation guarantee for ${\mathrm{\ell }}_p$ subspace approximation when $p\in \{1,2\}$. Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any $p\in [1,\mathrm{\infty })$.