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$. We show the following:
On the algorithmic side, for $p \in (0,2)$, we give the first
$n^{\text{poly}(k/\epsilon)}$ time $(1+\epsilon)$-approximation algorithm. For
$p = 0$, there are various problem formulations, a common one being the binary
setting for which $A\in\{0,1\}^{n\times d}$ and $B = U \cdot V$, where
$U\in\{0,1\}^{n \times k}$ and $V\in\{0,1\}^{k \times d}$. There are also
various notions of multiplication $U \cdot V$, such as a matrix product over
the reals, over a finite field, or over a Boolean semiring. We give the first
PTAS for what we call the Generalized Binary $\ell_0$-Rank-$k$ Approximation
problem, for which these variants are special cases. Our algorithm runs in time
$(1/\epsilon)^{2^{O(k)}/\epsilon^{2}} \cdot nd \cdot \log^{2^k} d$. For the
specific case of finite fields of constant size, we obtain an alternate
algorithm with time $n \cdot d^{\text{poly}(k/\epsilon)}$.
On the hardness front, for $p \in (1,2)$, we show under the Small Set
Expansion Hypothesis and Exponential Time Hypothesis (ETH), there is no
constant factor approximation algorithm running in time $2^{k^{\delta}}$ for a
constant $\delta > 0$, showing an exponential dependence on $k$ is necessary.
For $p = 0$, we observe that there is no approximation algorithm for the
Generalized Binary $\ell_0$-Rank-$k$ Approximation problem running in time
$2^{2^{\delta k}}$ for a constant $\delta > 0$. We also show for finite fields
of constant size, under the ETH, that any fixed constant factor approximation
algorithm requires $2^{k^{\delta}}$ time for a constant $\delta > 0$.

Token crowdsale for this paper ends in

Are you an author of this paper? Check the Twitter handle we have for you is correct.

Frank Ban | (add twitter) | |

Vijay Bhattiprolu | (add twitter) | |

Karl Bringmann | (add twitter) | |

Pavel Kolev | (add twitter) | |

Euiwoong Lee | (add twitter) | |

David P. Woodruff | (add twitter) |

Ask the authors of this paper a question or leave a comment.

User:

None
(add)

Repo:

None
(add)

Stargazers:

0

Forks:

0

Open Issues:

0

Network:

0

Subscribers:

0

Language:

None

Sample Sizes (N=):

Inserted:

Words Total:

Words Unique:

Source:

Abstract:

Nobody has tweeted about this paper.