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.
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).
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
letterdataset 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