Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products
- URL: http://arxiv.org/abs/2311.01960v1
- Date: Fri, 3 Nov 2023 14:56:24 GMT
- Title: Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products
- Authors: Tamas Sarlos, Xingyou Song, David Woodruff, Qiuyi (Richard) Zhang
- Abstract summary: Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting.
We give novel reductions from the Strong Exponential Time Hypothesis (SETH) that rely on lower bounding the leverage scores of flat sparse vectors.
Since our low rank algorithms rely on matrix-vectors, our lower bounds extend to show that computing $f(UV)W$, for even a small matrix $W$, requires $Omega(n2-o(1))$ time.
- Score: 9.661328973620531
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
We show that our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$.
In particular, our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$.
Our main algorithm can be viewed as a randomized block coordinate descent method.
arXiv Detail & Related papers (2023-12-14T12:53:34Z) - Quantum and classical query complexities of functions of matrices [0.0]
We show that for any continuous function $f(x):[-1,1]rightarrow [-1,1]$, the quantum query complexity of computing $brai f(A) ketjpm varepsilon/4$ is lower bounded by $Omega(widetildedeg_varepsilon(f))$.
arXiv Detail & Related papers (2023-11-13T00:45:41Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem.
The goal is to approximate $mathbfA$ as a product of low-rank factors.
Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z) - Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
We show that any algorithm requires $Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods.
Our lower bound addresses Open Question 1WooWoo14, providing evidence for the lack of progress on algorithms for Spectral LRA.
arXiv Detail & Related papers (2023-04-06T16:15:19Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
inner product attention computation is a fundamental task for training large language models such as Transformer, GPT-1, BERT, GPT-2, GPT-3 and ChatGPT.
We investigate whether faster algorithms are possible by implicitly making use of the matrix $A$.
This gives a theoretical explanation for the phenomenon observed in practice that attention computation is much more efficient when the input matrices have smaller entries.
arXiv Detail & Related papers (2023-02-26T02:42:39Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem.
We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
arXiv Detail & Related papers (2022-04-13T22:18:47Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm.
Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$.
We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
arXiv Detail & Related papers (2021-05-17T16:40:48Z) - Sparse sketches with small inversion bias [79.77110958547695]
Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance.
We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices.
We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
arXiv Detail & Related papers (2020-11-21T01:33:15Z) - Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank
Approximation [0.0]
We give the first time column subset selection-based $ell_p$ low rank approximation algorithm sampling $tildeO(k)$ 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$.
arXiv Detail & Related papers (2020-07-20T17:50:30Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $nOmega(1)$ number of columns.
We show that under certain minimal and realistic distributional settings, it is possible to obtain a $(k/epsilon)$-approximation with a nearly linear running time and poly$(k/epsilon)+O(klog n)$ columns.
This is the first algorithm of any kind for achieving a $(k/epsilon)$-approximation for entrywise
arXiv Detail & Related papers (2020-04-16T22:57:06Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.