论文标题
$ \ ell_ {p} $子空间近似的一通添加词子集选择
One-pass additive-error subset selection for $\ell_{p}$ subspace approximation
论文作者
论文摘要
我们考虑$ \ ell_ {p} $子空间近似的子集选择问题，也就是说，可以有效地找到数据点的\ emph {small}子集，从而使该子集最佳地解决该问题可为原始输入最佳地解决问题提供良好的近似值。先前已知的子集选择算法基于音量采样和自适应采样\ cite {deshpandev07}，对于[1，\ infty）$的一般情况，需要多次通过数据。在本文中，我们为$ \ ell_ {p} $ subspace近似值提供了一个通用子集选择，用于[1，\ infty）$中的任何$ p \ subspace近似。在特殊情况下，提供一通乘法$（1+ε）$近似工作的早期子集选择算法。 cohen \ textit {et al。} \ cite {cohenmm17}给出了一个单通子子集，为$ \ ell_ {2} $ subspace近似值的特殊情况提供了乘法$（1+ε）$近似保证。 mahabadi \ textit {et al。} \ cite {mahabadirwz20}给出一个单pass \ emph \ emph {noisy}子集选择，并提供$（1+ε）$近似保证，用于$ \ ell_ {p} $ p} $ p \ in $ p \ in \ in \ in \ in \ in \ in \ in \ in \ in \ in \ in \ in \ in。我们的子集选择算法提供了较弱的添加近似保证，但它适用于[1，\ infty）$中的任何$ p \。
We consider the problem of subset selection for $\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 $\ell_{p}$ subspace approximation, for any $p \in [1, \infty)$. Earlier subset selection algorithms that give a one-pass multiplicative $(1+ε)$ approximation work under the special cases. Cohen \textit{et al.} \cite{CohenMM17} gives a one-pass subset section that offers multiplicative $(1+ε)$ approximation guarantee for the special case of $\ell_{2}$ subspace approximation. Mahabadi \textit{et al.} \cite{MahabadiRWZ20} gives a one-pass \emph{noisy} subset selection with $(1+ε)$ approximation guarantee for $\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, \infty)$.
