Sketching Transformed Matrices with Applications to Natural Language Processing

Abstract

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.

AISTATS 2020

References in corpus (21)

• Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
• Enriching Word Vectors with Subword Information
• Robust VIF regression with application to variable selection in large data sets
• Optimal CUR Matrix Decompositions
• Recursive Sketching For Frequency Moments
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Input Sparsity and Hardness for Robust Subspace Approximation
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Solving Tall Dense Linear Programs in Nearly Linear Time
• Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
• Sample-Optimal Low-Rank Approximation of Distance Matrices
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• Twice-Ramanujan Sparsifiers
• Leverage Score Sampling for Faster Accelerated Regression and ERM
• Towards a Zero-One Law for Column Subset Selection
• Algorithms for ${\ell }_p$ Low Rank Approximation
• Total Least Squares Regression in Input Sparsity Time
• Dimensionality Reduction for Tukey Regression
• A near-optimal algorithm for approximating the John Ellipsoid
• Average Case Column Subset Selection for Entrywise ${\ell }_1$-Norm Loss
• A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees