Single Pass Entrywise-Transformed Low Rank Approximation
- URL: http://arxiv.org/abs/2107.07889v1
- Date: Fri, 16 Jul 2021 13:22:29 GMT
- Title: Single Pass Entrywise-Transformed Low Rank Approximation
- Authors: Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff
- Abstract summary: Liang et al. shows how to find a rank-$k$ factorization to $f(A)$ for an $n times n$ matrix $A$ using only $n cdot operatornamepoly(epsilon-1klog n)$ words of memory, with overall error $10|f(A)-[f(A)]_k|_1,22$, where $[f(A)]_k$ is the best rank-$k$ approximation to $f(A)$ and $
- Score: 44.14819869788393
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In applications such as natural language processing or computer vision, one
is given a large $n \times d$ matrix $A = (a_{i,j})$ and would like to compute
a matrix decomposition, e.g., a low rank approximation, of a function $f(A) =
(f(a_{i,j}))$ applied entrywise to $A$. A very important special case is the
likelihood function $f\left( A \right ) = \log{\left( \left| a_{ij}\right|
+1\right)}$. A natural way to do this would be to simply apply $f$ to each
entry of $A$, and then compute the matrix decomposition, but this requires
storing all of $A$ as well as multiple passes over its entries. Recent work of
Liang et al.\ shows how to find a rank-$k$ factorization to $f(A)$ for an $n
\times n$ matrix $A$ using only $n \cdot \operatorname{poly}(\epsilon^{-1}k\log
n)$ words of memory, with overall error $10\|f(A)-[f(A)]_k\|_F^2 +
\operatorname{poly}(\epsilon/k) \|f(A)\|_{1,2}^2$, where $[f(A)]_k$ is the best
rank-$k$ approximation to $f(A)$ and $\|f(A)\|_{1,2}^2$ is the square of the
sum of Euclidean lengths of rows of $f(A)$. Their algorithm uses three passes
over the entries of $A$. The authors pose the open question of obtaining an
algorithm with $n \cdot \operatorname{poly}(\epsilon^{-1}k\log n)$ words of
memory using only a single pass over the entries of $A$. In this paper we
resolve this open question, obtaining the first single-pass algorithm for this
problem and for the same class of functions $f$ studied by Liang et al.
Moreover, our error is $\|f(A)-[f(A)]_k\|_F^2 + \operatorname{poly}(\epsilon/k)
\|f(A)\|_F^2$, where $\|f(A)\|_F^2$ is the sum of squares of Euclidean lengths
of rows of $f(A)$. Thus our error is significantly smaller, as it removes the
factor of $10$ and also $\|f(A)\|_F^2 \leq \|f(A)\|_{1,2}^2$. We also give an
algorithm for regression, pointing out an error in previous work, and
empirically validate our results.
Related papers
- 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) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$.
We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
arXiv Detail & Related papers (2024-10-07T19:47:13Z) - 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) - 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) - 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.