Improving TensorSketch Using Complex Random Variables

textttTensorSketch by~citepham2013fast,kar2012random provides efficient sketching algorithms for high-dimensional polynomial kernels vecxotimes p ∈ Rdp. citekar2012random uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost O(pDd), where D denotes the sketch dimension, whereas~citepham2013fast extends the sparse textttCountSketch~citepcountsketch algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time Obig(p(nnzvecx + D log D)big). However, the variance of both estimators grows exponentially with the polynomial degree p, scaling as 3p/D. Recent work by~citepmlr-v206-wacker23a showed that using complex-valued distribution reduces this dependence to 2p/D for the approach of~citekar2012random. However, their method relies on dense JL-type projections with computational cost O(pDd) and does not extend to the algorithm of~citepham2013fast. In this work, we introduce a simple variant of textttTensorSketch~citeppham2013fast that achieves the same variance bound as~citepmlr-v206-wacker23a, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.