Introduction
In many machine learning applications, we frequently encounter large, low-rank matrices represented as $A = UV^\top$ (where $U$ and $V$ are "tall and thin" matrices). A common operation is applying a non-linear scalar function $f$ to every single entry of that matrix, resulting in a new matrix $f^\odot(A)$. Examples include applying a sigmoid activation in a neural network or computing an RBF kernel.
This presents a significant computational challenge. Even if the original matrix $A$ is low-rank, the element-wise transformed matrix $f^\odot(A)$ usually is not. Computing all $n^2$ entries explicitly is prohibitively slow for large datasets, requiring $O(n^2)$ time complexity. Furthermore, "element-wise" functions lack the clean algebraic properties of traditional matrix functions (which operate on eigenvalues), making them mathematically harder to approximate.
To solve this, researchers have introduced POLY-TENSORSKETCH, a novel algorithm designed to approximate element-wise non-linear functions of low-rank matrices in sub-quadratic $o(n^2)$ time. By combining polynomial approximation with randomized tensor sketching and a clever "coreset-based" ridge regression, the method achieves significant speedups while maintaining higher accuracy than standard techniques like Random Fourier Features (RFF).
The POLY-TENSORSKETCH Methodology
The authors propose a function-agnostic, three-step approach to bypass the $O(n^2)$ bottleneck:
1. Polynomial Approximation
First, the target non-linear function $f(x)$ is represented as a polynomial $p_r(x) = \sum_{j=0}^r c_j x^j$. This allows the algorithm to break down complex functions into manageable algebraic components.
2. TensorSketch for Monomials
To handle the $x^j$ terms efficiently, the authors utilize TensorSketch, a randomized algorithm capable of approximating the power of a dot product. This allows them to sketch the "monomial" parts of the matrix without explicitly computing the full high-dimensional expansions.
3. Optimal Coefficient Regression via Coresets
This is the core innovation of the paper. A fundamental tension exists in polynomial sketching: higher-degree polynomials offer better theoretical accuracy but cause the TensorSketch variance (error) to grow exponentially. Standard Taylor or Chebyshev series coefficients fail to account for this sketching noise.
To fix this, the authors formulate a Generalized Ridge Regression problem that balances the error of the polynomial fit against the variance of the sketch. To solve this regression in linear $O(n)$ time rather than $O(n^2)$ time, they use a "greedy k-center" algorithm to select a small, representative subset of rows—a coreset—to find the optimal coefficients $c_j$. Additionally, they perform this regression using a Chebyshev basis rather than standard monomials to ensure numerical stability and prevent values from blowing up.
Key Results and Performance
The authors evaluated POLY-TENSORSKETCH across several domains, including synthetic kernels, real-world classification datasets (like segment and usps), optimal transport (Sinkhorn distances), and neural network compression.
- Superior Accuracy: In RBF kernel approximation tasks, POLY-TENSORSKETCH (labeled Coreset-TS) consistently outperformed Random Fourier Features (RFF) and standard Taylor/Chebyshev methods. It often achieved relative errors several orders of magnitude smaller for the exact same computational budget.
- Massive Speedups: For Kernel SVM classification tasks, the proposed method provided speedups of up to 50x compared to exact methods, with only a marginal loss in classification accuracy.
- Algorithmic Stability: In Sinkhorn algorithm tests used for optimal transport, POLY-TENSORSKETCH remained highly stable across different matrix dimensions. In contrast, baseline methods like Nyström or RFF exhibited high variance and instability.
- Neural Network Linearization: The authors successfully replaced non-linear activation layers in an AlexNet model (trained on CIFAR-100) with their linearized sketch. This reduced inference complexity while outperforming a simple vanilla linear model.
Limitations and Future Directions
While highly effective, the method relies heavily on the input matrix $A$ being low-rank (or having a strong low-rank approximation). If the input data is inherently high-rank, the computational benefits of sketching diminish. Additionally, highly complex functions might still require a large polynomial degree $r$, which increases the sketch dimension and computational cost.
Future work suggested by the authors includes exploring more complex neural network architectures and investigating whether this sketching technique can be integrated directly into the training process of deep models, potentially creating inherently "sketch-friendly" representations from the ground up.
Summary updated