论文标题
通用案例列子集选择入门$ \ ell_1 $ -norm损失
Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss
论文作者
论文摘要
我们研究了有关入口的列子集选择问题$ \ ell_1 $ - norm损失。众所周知，在最坏的情况下，要获得矩阵的良好排名-K $近似值，人们需要一个任意的$ n^{ω（1）} $列数以获得$（1+ε）$ - 近似值至最佳入口$ \ ell_ ell_1 $ - ell_1 $ - norm-norm低级级别的$ n $ n $ n \ times n $ matrix。尽管如此，我们表明，在某些最小和现实的分配设置下，可以获得$（1+ε）$ - 近似值，几乎是线性运行时间和poly $（k/ε）+o（k \ log n）$列。即，我们表明，如果输入矩阵$ a $具有$ a = b + e $的表格，其中$ b $是任意排名-K $矩阵，而$ e $是I.I.D的矩阵。从任何分布的$μ$中得出的条目（1+γ）$ - 对于任意小的常数$γ> 0 $存在，然后可以在几乎线性的时间内获得$（1+ε）$ - 近似列子集选择$（1+ε）$。相反，我们表明，如果不存在第一时刻，那么即使选择任何$ n^{o（1）} $列，也无法获得$（1+ε）$ - 近似子集选择算法。这是任何类型的算法，用于实现$（1+ε）$ - 进入入口的近似值$ \ ell_1 $ - norm损失低级近似值。
We study the column subset selection problem with respect to the entrywise $\ell_1$-norm loss. It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $n^{Ω(1)}$ number of columns to obtain a $(1+ε)$-approximation to the best entrywise $\ell_1$-norm low rank approximation of an $n \times n$ matrix. Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a $(1+ε)$-approximation with a nearly linear running time and poly$(k/ε)+O(k\log n)$ columns. Namely, we show that if the input matrix $A$ has the form $A = B + E$, where $B$ is an arbitrary rank-$k$ matrix, and $E$ is a matrix with i.i.d. entries drawn from any distribution $μ$ for which the $(1+γ)$-th moment exists, for an arbitrarily small constant $γ> 0$, then it is possible to obtain a $(1+ε)$-approximate column subset selection to the entrywise $\ell_1$-norm in nearly linear time. Conversely we show that if the first moment does not exist, then it is not possible to obtain a $(1+ε)$-approximate subset selection algorithm even if one chooses any $n^{o(1)}$ columns. This is the first algorithm of any kind for achieving a $(1+ε)$-approximation for entrywise $\ell_1$-norm loss low rank approximation.
