Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix

This paper studies how to sketch element-wise functions of low-rank matrices. Formally, given low-rank matrix A = [A ij ] and scalar non-linear function f , we aim for finding an approximated low-rank representation of the (possibly highrank) matrix [f (A ij )]. To this end, we propose an efficient sketching-based algorithm whose complexity is significantly lower than the number of entries of A, i.e., it runs without accessing all entries of [f (A ij )] explicitly. The main idea underlying our method is to combine a polynomial approximation of f with the existing tensor sketch scheme for approximating monomials of entries of A. To balance the errors of the two approximation components in an optimal manner, we propose a novel regression formula to find polynomial coefficients given A and f . In particular, we utilize a coreset-based regression with a rigorous approximation guarantee. Finally, we demonstrate the applicability and superiority of the proposed scheme under various machine learning tasks. * In this paper, we primarily focus on the square matrix A for simplicity, but it is straightforward to extend our results to the case of non-square matrices.