Improving TensorSketch Using Complex Random Variables

TensorSketch by \cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels \vec{x}^{\otimes p} \in \R^{d^p}. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost O(pDd), where D denotes the sketch dimension, whereas \cite{pham2013fast} extends the sparse CountSketch \citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time O\big(p(\nnz{\vec{x}} + D \log D)\big). However, the variance of both estimators grows exponentially with the polynomial degree p, scaling as 3^{p}/D. Recent work by \cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to 2^{p}/D for the approach of \cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost O(pDd) and does not extend to the algorithm of \cite{pham2013fast}. In this work, we introduce a simple variant of TensorSketch \citep{pham2013fast} that achieves the same variance bound as \cite{pmlr-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.