Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose $\mathit{\text{Tensor}}\mathit{\text{Sketch}}$, an efficient random feature map for approximating polynomial kernels. Given $n$ training samples in ${\mathbb{R}}^d$ Tensor Sketch computes low-dimensional embeddings in ${\mathbb{R}}^D$ in time $\mathcal{O}(n(d+D\log D))$ making it well-suited for high-dimensional and large-scale settings. We provide theoretical guarantees on the approximation error, ensuring the fidelity of the resulting kernel function estimates. We also discuss extensions and highlight applications where Tensor Sketch serves as a central computational tool.