# Item

ITEM ACTIONSEXPORT

Released

Paper

#### A PTAS for l p-Low Rank Approximation

##### External Ressource

No external resources are shared

##### Fulltext (public)

arXiv:1807.06101.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ban, F., Bhattiprolu, V., Bringmann, K., Kolev, P., Lee, E., & Woodruff, D. P. (2018). A PTAS for l p-Low Rank Approximation. Retrieved from http://arxiv.org/abs/1807.06101.

Cite as: http://hdl.handle.net/21.11116/0000-0002-9D17-4

##### Abstract

A number of recent works have studied algorithms for entrywise $\ell_p$-low
rank approximation, namely, algorithms which given an $n \times d$ matrix $A$
(with $n \geq d$), output a rank-$k$ matrix $B$ minimizing
$\|A-B\|_p^p=\sum_{i,j}|A_{i,j}-B_{i,j}|^p$ when $p > 0$; and
$\|A-B\|_0=\sum_{i,j}[A_{i,j}\neq B_{i,j}]$ for $p=0$.
On the algorithmic side, for $p \in (0,2)$, we give the first
$(1+\epsilon)$-approximation algorithm running in time
$n^{\text{poly}(k/\epsilon)}$. Further, for $p = 0$, we give the first
almost-linear time approximation scheme for what we call the Generalized Binary
$\ell_0$-Rank-$k$ problem. Our algorithm computes $(1+\epsilon)$-approximation
in time $(1/\epsilon)^{2^{O(k)}/\epsilon^{2}} \cdot nd^{1+o(1)}$.
On the hardness of approximation side, for $p \in (1,2)$, assuming the Small
Set Expansion Hypothesis and the Exponential Time Hypothesis (ETH), we show
that there exists $\delta := \delta(\alpha) > 0$ such that the entrywise
$\ell_p$-Rank-$k$ problem has no $\alpha$-approximation algorithm running in
time $2^{k^{\delta}}$.