Single Pass Entrywise-Transformed Low Rank Approximation

Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David Woodruff
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:4982-4991, 2021.

Abstract

In applications such as natural language processing or computer vision, one is given a large n×n matrix A=(ai,j) and would like to compute a matrix decomposition, e.g., a low rank approximation, of a function f(A)=(f(ai,j)) applied entrywise to A. A very important special case is the likelihood function f(A)=log(|aij|+1). 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) using only n⋅\poly(\eps−1klogn) words of memory, with overall error 10‖, 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 3 passes over the entries of A. The authors pose the open question of obtaining an algorithm with n \cdot \poly(\eps^{-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 + \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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-jiang21f, title = {Single Pass Entrywise-Transformed Low Rank Approximation}, author = {Jiang, Yifei and Li, Yi and Sun, Yiming and Wang, Jiaxin and Woodruff, David}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {4982--4991}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/jiang21f/jiang21f.pdf}, url = {https://proceedings.mlr.press/v139/jiang21f.html}, abstract = {In applications such as natural language processing or computer vision, one is given a large $n \times n$ 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)$ using only $n \cdot \poly(\eps^{-1}k\log n)$ words of memory, with overall error $10\|f(A)-[f(A)]_k\|_F^2 + \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 $3$ passes over the entries of $A$. The authors pose the open question of obtaining an algorithm with $n \cdot \poly(\eps^{-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 + \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$.} }
Endnote
%0 Conference Paper %T Single Pass Entrywise-Transformed Low Rank Approximation %A Yifei Jiang %A Yi Li %A Yiming Sun %A Jiaxin Wang %A David Woodruff %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-jiang21f %I PMLR %P 4982--4991 %U https://proceedings.mlr.press/v139/jiang21f.html %V 139 %X In applications such as natural language processing or computer vision, one is given a large $n \times n$ 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)$ using only $n \cdot \poly(\eps^{-1}k\log n)$ words of memory, with overall error $10\|f(A)-[f(A)]_k\|_F^2 + \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 $3$ passes over the entries of $A$. The authors pose the open question of obtaining an algorithm with $n \cdot \poly(\eps^{-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 + \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$.
APA
Jiang, Y., Li, Y., Sun, Y., Wang, J. & Woodruff, D.. (2021). Single Pass Entrywise-Transformed Low Rank Approximation. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:4982-4991 Available from https://proceedings.mlr.press/v139/jiang21f.html.

Related Material