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

Insu Han, Haim Avron, Jinwoo Shin

Abstract

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.

Introduction

In large-scale machine learning, data is often represented by $n \times n$ matrices that are approximately low-rank, $A \approx UV^\top$. However, many algorithms require applying a non-linear function $f$ to every entry of $A$. Even if $A$ is low-rank, the resulting matrix $f(A)$ typically is not, making the computation of all $n^2$ entries prohibitively expensive. While methods exist for spectral matrix functions, element-wise functions have lacked a general, efficient sketching framework that avoids full matrix materialization.

Methodology: POLY-TENSORSKETCH

The proposed POLY-TENSORSKETCH algorithm approximates $f(x)$ using a polynomial $p_r(x) = \sum_{j=0}^r c_j x^j$. To avoid explicit computation of high-degree monomials, it leverages TensorSketch, a randomized technique that approximates the low-rank structure of monomials in $O(n)$ time.

A core innovation of this work is addressing the variance-bias trade-off inherent in polynomial sketching. While higher-degree polynomials reduce approximation bias, they exponentially increase the variance of the TensorSketch. To optimize this, the authors formulate a Generalized Ridge Regression problem to select coefficients $c_j$ that minimize both fitting error and sketching variance. This is solved efficiently using coreset regression, which identifies a small, representative subset of entries to determine optimal coefficients without scanning the entire matrix.

Relative error vs. polynomial degree $r$ for the segment dataset, demonstrating the stability of the Coreset-TS approach.

Key Results and Performance

The researchers evaluated POLY-TENSORSKETCH on synthetic data and UCI benchmarks such as segment and usps. The method was compared against Random Fourier Features (RFF) and standard polynomial expansions (Taylor and Chebyshev).

Comprehensive evaluation of relative error across synthetic, segment, and usps datasets under varying sketch dimensions, polynomial degrees, and scaling factors.

As shown in the experimental results, the Coreset-TS method consistently outperforms RFF and other polynomial sketches in terms of relative error. Key highlights include:

  • Kernel SVM: Achieved a 40x speedup on the letter dataset compared to exact methods, with lower classification error than RFF.
  • Optimal Transport: Provided a more stable and accurate alternative to the Nyström method within the Sinkhorn algorithm.
  • Neural Network Linearization: Successfully approximated activation functions in an AlexNet model, enabling faster inference on CIFAR100 while maintaining competitive accuracy.

Conclusion

POLY-TENSORSKETCH offers a powerful framework for approximating element-wise functions of low-rank matrices. By combining polynomial approximation with variance-aware coefficient selection, it enables significant computational savings without sacrificing accuracy. While its efficiency depends on the low-rank nature of the input and the smoothness of the target function, it represents a major step forward in scalable matrix operations for machine learning.

Summary updated

Abstract

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.
BibTeX
@inproceedings{han2020polynomial,
  author = {Insu Han and Haim Avron and Jinwoo Shin},
  title = {{Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=MFnHK3kV-He},
}
Figure