Inspired by fast algorithms in natural language processing, we study low rank
approximation in the entrywise transformed setting where we want to find a good
rank $k$ approximation to $f(U \cdot V)$, where $U, V^\top \in \mathbb{R}^{n
\times r}$ are given, $r = O(\log(n))$, and $f(x)$ is a general scalar
function. Previous work in sublinear low rank approximation has shown that if
both (1) $U = V^\top$ and (2) $f(x)$ is a PSD kernel function, then there is an
$O(nk^{\omega-1})$ time constant relative error approximation algorithm, where
$\omega \approx 2.376$ is the exponent of matrix multiplication. We give the
first conditional time hardness results for this problem, demonstrating that
both conditions (1) and (2) are in fact necessary for getting better than
$n^{2-o(1)}$ time for a relative error low rank approximation for a wide class
of functions. We give novel reductions from the Strong Exponential Time
Hypothesis (SETH) that rely on lower bounding the leverage scores of flat
sparse vectors and hold even when the rank of the transformed matrix $f(UV)$
and the target rank are $n^{o(1)}$, and when $U = V^\top$. Furthermore, even
when $f(x) = x^p$ is a simple polynomial, we give runtime lower bounds in the
case when $U \neq V^\top$ of the form $\Omega(\min(n^{2-o(1)}, \Omega(2^p)))$.
Lastly, we demonstrate that our lower bounds are tight by giving an $O(n \cdot
\text{poly}(k, 2^p, 1/\epsilon))$ time relative error approximation algorithm
and a fast $O(n \cdot \text{poly}(k, p, 1/\epsilon))$ additive error
approximation using fast tensor-based sketching. Additionally, since our low
rank algorithms rely on matrix-vector product subroutines, our lower bounds
extend to show that computing $f(UV)W$, for even a small matrix $W$, requires
$\Omega(n^{2-o(1)})$ time.

在输入转换设置中，我们研究低秩逼近，给出了该问题的条件时间难度结果和运行时下界，同时证明了这些下界是紧致的，并提供了使用基于张量的草图的相对误差逼近算法。