A PTAS for $\ell_p$-Low Rank Approximation
This work addresses computational challenges in matrix approximation for machine learning and data analysis, offering new algorithmic solutions and theoretical limits.
The paper tackles the problem of entrywise ℓp-low rank approximation for matrices, providing the first (1+ε)-approximation algorithms with specific time complexities for p in (0,2) and p=0, and showing hardness results for p in (1,2) under certain hypotheses.
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+ε)$-approximation algorithm running in time $n^{\text{poly}(k/ε)}$. 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+ε)$-approximation in time $(1/ε)^{2^{O(k)}/ε^{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 $δ:= δ(α) > 0$ such that the entrywise $\ell_p$-Rank-$k$ problem has no $α$-approximation algorithm running in time $2^{k^δ}$.