Improving TensorSketch Using Complex Random Variables

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

Related

• An Ensembled Latent Factor Model via Differential Evolution and Gradient Descent Optimization
• Formally Verifying Analog Neural Networks Under Process Variations Using Polynomial Zonotopes

Source: arXiv cs.AI | 2026-08-12