Krylov Methods are (nearly) Optimal for Low-Rank Approximation
- URL: http://arxiv.org/abs/2304.03191v1
- Date: Thu, 6 Apr 2023 16:15:19 GMT
- Title: Krylov Methods are (nearly) Optimal for Low-Rank Approximation
- Authors: Ainesh Bakshi and Shyam Narayanan
- Abstract summary: 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.
- Score: 8.017116107657206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of rank-$1$ low-rank approximation (LRA) in the
matrix-vector product model under various Schatten norms: $$
\min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal{S}_p} , $$ where
$\|M\|_{\mathcal{S}_p}$ denotes the $\ell_p$ norm of the singular values of
$M$. Given $\varepsilon>0$, our goal is to output a unit vector $v$ such that
$$
\|A(I - vv^\top)\|_{\mathcal{S}_p} \leq (1+\varepsilon) \min_{\|u\|_2=1}\|A(I
- u u^\top)\|_{\mathcal{S}_p}. $$ Our main result shows that Krylov methods
(nearly) achieve the information-theoretically optimal number of matrix-vector
products for Spectral ($p=\infty$), Frobenius ($p=2$) and Nuclear ($p=1$) LRA.
In particular, for Spectral LRA, we show that any algorithm requires
$\Omega\left(\log(n)/\varepsilon^{1/2}\right)$ matrix-vector products, exactly
matching the upper bound obtained by Krylov methods [MM15, BCW22]. Our lower
bound addresses Open Question 1 in [Woo14], providing evidence for the lack of
progress on algorithms for Spectral LRA and resolves Open Question 1.2 in
[BCW22]. Next, we show that for any fixed constant $p$, i.e. $1\leq p =O(1)$,
there is an upper bound of
$O\left(\log(1/\varepsilon)/\varepsilon^{1/3}\right)$ matrix-vector products,
implying that the complexity does not grow as a function of input size. This
improves the $O\left(\log(n/\varepsilon)/\varepsilon^{1/3}\right)$ bound
recently obtained in [BCW22], and matches their
$\Omega\left(1/\varepsilon^{1/3}\right)$ lower bound, to a
$\log(1/\varepsilon)$ factor.
Related papers
- Fast, robust approximate message passing [2.668787455520979]
We give a fast, spectral procedure for implementing approximate-message passing (AMP) algorithms robustly.
Our algorithm performs a spectral pre-processing step and mildly modifies the perturbeds of $mathcal A$.
arXiv Detail & Related papers (2024-11-05T03:20:14Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$.
As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
We study the problem of residual error estimation for matrix and vector norms using a linear sketch.
We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work.
We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
arXiv Detail & Related papers (2024-08-16T02:33:07Z) - Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
A random $mtimes n$ matrix $S$ is an oblivious subspace embedding (OSE)
We show that an $mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$.
We use this to construct the first oblivious subspace embedding with $O(d)$ embedding dimension that can be applied faster than current matrix multiplication time.
arXiv Detail & Related papers (2023-11-17T18:01:58Z) - Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products [9.661328973620531]
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.
arXiv Detail & Related papers (2023-11-03T14:56:24Z) - 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) - 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) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
In this paper, we investigate the sample complexity of policy evaluation in offline reinforcement learning.
Under the low distribution shift assumption, we show that there is an algorithm that needs at most $Oleft(maxleft fracleftVert thetapirightVert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$ samples to approximate the
arXiv Detail & Related papers (2021-03-17T18:18:57Z) - 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.