Single Pass Entrywise-Transformed Low Rank Approximation
share
In applications such as natural language processing or computer vision, one is given a large n × 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( A ) = log( | a_ij| +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) for an n × n matrix A using only n ·poly(ϵ^-1klog n) words of memory, with overall error 10f(A)-[f(A)]_k_F^2 + poly(ϵ/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 ·poly(ϵ^-1klog 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(ϵ/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 ≤f(A)_1,2^2. We also give an algorithm for regression, pointing out an error in previous work, and empirically validate our results.
READ FULL TEXT