论文标题
最佳$ \ ell_1 $列子集选择和低级近似的快速PTA
Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
论文作者
论文摘要
我们研究进入的问题$ \ ell_1 $低等级近似。我们给出了第一个多项式时间列子集选择基于$ \ ell_1 $低等级近似算法采样$ \ tilde {o}（k）$列并实现$ \ tilde {o}（k^{k^{1/2}）$ - 以前的$ k $ andem-k $ andem-k $ - 基于列子集选择的列下限$ \ ell_1 $ -low等级近似，该级别可容纳任何$ \ text {poly}（k）$列数。我们扩展了结果，以获取基于列的$ \ ell_p $低等级近似列的紧密上限和下限，任何$ 1 <p <2 $，在此问题上结束了一系列工作。 接下来，我们给出$（1 + \ varepsilon）$ - entrywise $ \ ell_p $低级近似值的近似算法，价格为$ 1 \ leq p <2 $，这不是列子集选择算法。首先，我们获得了一个算法，该算法给定一个矩阵$ a \ in \ mathbb {r}^{n \ times d} $，返回A rank -$ k $ k $ matrix $ \ hat {a} $ in $ 2^{\ text {\ text {poly}（poly}（k/\ varepsilon） \ hat {a} \ | _p \ leq（1 + \ varepsilon）\ cdot opt + \ frac {\ varepsilon} {\ text {poly} {poly}（k）} \ | a \ | a \ | a \ | _p $ _p $ _p $ _p $ _p $ ___ Using this algorithm, in the same running time we give an algorithm which obtains error at most $(1 + \varepsilon) \cdot OPT$ and outputs a matrix of rank at most $3k$ -- these algorithms significantly improve upon all previous $(1 + \varepsilon)$- and $O(1)$-approximation algorithms for the $\ell_p$ low rank approximation问题，它至少需要$ n^{\ text {poly}（k/\ varepsilon）} $或$ n^{\ text {poly}（k）} $运行时间，并且需要强的位复杂性假设（我们的算法没有），或者Bicriteria bicriteria bicriteria nop bicriteria cark rack $ 3k $ $ 3K $。最后，我们显示的硬度结果几乎与我们的$ 2^{\ text {poly}（k）} + \ text {poly}（nd）$运行时间和上述加法错误保证。
We study the problem of entrywise $\ell_1$ low rank approximation. We give the first polynomial time column subset selection-based $\ell_1$ low rank approximation algorithm sampling $\tilde{O}(k)$ columns and achieving an $\tilde{O}(k^{1/2})$-approximation for any $k$, improving upon the previous best $\tilde{O}(k)$-approximation and matching a prior lower bound for column subset selection-based $\ell_1$-low rank approximation which holds for any $\text{poly}(k)$ number of columns. We extend our results to obtain tight upper and lower bounds for column subset selection-based $\ell_p$ low rank approximation for any $1 < p < 2$, closing a long line of work on this problem. We next give a $(1 + \varepsilon)$-approximation algorithm for entrywise $\ell_p$ low rank approximation, for $1 \leq p < 2$, that is not a column subset selection algorithm. First, we obtain an algorithm which, given a matrix $A \in \mathbb{R}^{n \times d}$, returns a rank-$k$ matrix $\hat{A}$ in $2^{\text{poly}(k/\varepsilon)} + \text{poly}(nd)$ running time such that: $$\|A - \hat{A}\|_p \leq (1 + \varepsilon) \cdot OPT + \frac{\varepsilon}{\text{poly}(k)}\|A\|_p$$ where $OPT = \min_{A_k \text{ rank }k} \|A - A_k\|_p$. Using this algorithm, in the same running time we give an algorithm which obtains error at most $(1 + \varepsilon) \cdot OPT$ and outputs a matrix of rank at most $3k$ -- these algorithms significantly improve upon all previous $(1 + \varepsilon)$- and $O(1)$-approximation algorithms for the $\ell_p$ low rank approximation problem, which required at least $n^{\text{poly}(k/\varepsilon)}$ or $n^{\text{poly}(k)}$ running time, and either required strong bit complexity assumptions (our algorithms do not) or had bicriteria rank $3k$. Finally, we show hardness results which nearly match our $2^{\text{poly}(k)} + \text{poly}(nd)$ running time and the above additive error guarantee.
