Sketching Transformed Matrices with Applications to Natural Language Processing
This addresses a bottleneck in machine learning applications like NLP word embeddings, where handling transformed matrices (e.g., PMI) is space-intensive, offering a general solution rather than application-specific redesigns.
The paper tackles the problem of computing matrix decompositions for entrywise-transformed large matrices that cannot be stored in memory, proposing a space-efficient sketching algorithm for matrix products with provable error bounds and applying it to low-rank approximation, achieving small error and efficiency in space and time as validated by experiments.
Suppose we are given a large matrix $A=(a_{i,j})$ that cannot be stored in memory but is in a disk or is presented in a data stream. However, we need to compute a matrix decomposition of the entry-wisely transformed matrix, $f(A):=(f(a_{i,j}))$ for some function $f$. Is it possible to do it in a space efficient way? Many machine learning applications indeed need to deal with such large transformed matrices, for example word embedding method in NLP needs to work with the pointwise mutual information (PMI) matrix, while the entrywise transformation makes it difficult to apply known linear algebraic tools. Existing approaches for this problem either need to store the whole matrix and perform the entry-wise transformation afterwards, which is space consuming or infeasible, or need to redesign the learning method, which is application specific and requires substantial remodeling. In this paper, we first propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. It works for a general family of transformations with provable small error bounds and thus can be used as a primitive in downstream learning tasks. We then apply this primitive to a concrete application: low-rank approximation. We show that our approach obtains small error and is efficient in both space and time. We complement our theoretical results with experiments on synthetic and real data.