Improving TensorSketch Using Complex Random Variables

摘要

by [Pham and Pagh, 2013, Kar and Karnick, 2012] provides efficient sketching algorithms for high-dimensional polynomial kernels 𝐱^⊗ p∈ℝ^d^p. [Kar and Karnick, 2012] uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost O(pDd), whereas [Pham and Pagh, 2013] extends the sparse [Charikar et al., 2004] algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time O(p(nnz(𝐱) + D log D)). However, the variance of both estimators grows exponentially with the polynomial degree p, scaling as 3^p/D, where D denotes the sketch dimension. Recent work by [Wacker et al., 2023] showed that using complex-valued distribution reduces this dependence to 2^p/D for the approach of [Kar and Karnick, 2012]. However, their method relies on dense JL-type projections with computational cost O(pDd) and does not extend to the algorithm of [Pham and Pagh, 2013]. In this work, we introduce a simple variant of [Pham and Pagh, 2013] that achieves the same variance bound as [Wacker et al., 2023], while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.