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

arXiv: https://arxiv.org/abs/1905.11616 · HTML: https://mlsanity.com/paper/1905.11616/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

## Built on by (most cited first, 7 of 7)

- [PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels](https://mlsanity.com/paper/2310.01655/) (2023)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity](https://mlsanity.com/paper/2406.15575/) (2024)
- [Random Features for the Neural Tangent Kernel](https://mlsanity.com/paper/2104.01351/) (2021)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)
- [Efficient Tensor Contraction via Fast Count Sketch](https://mlsanity.com/paper/2106.13062/) (2021)

## Abstract (arXiv)

This paper studies how to sketch element-wise functions of low-rank matrices. Formally, given low-rank matrix A = [Aij] and scalar non-linear function f, we aim for finding an approximated low-rank representation of the (possibly high-rank) matrix [f(Aij)]. 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(Aij)] 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.