Improving TensorSketch Using Complex Random Variables

Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:6178-6203, 2026.

Abstract

$\texttt{{TensorSketch}}$ by [Pham and Pagh, 2013, Kar and Karnick, 2012] provides efficient sketching algorithms for high-dimensional polynomial kernels $\mathbf{x}^{\otimes p} \in \mathbb{R}^{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 $\texttt{CountSketch}$ [Charikar et al., 2004] algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\operatorname{nnz}(\mathbf{x}) + D \log D)\big)$. 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 $\texttt{{TensorSketch}}$ [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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-sharma26b, title = {Improving {TensorSketch} Using Complex Random Variables}, author = {Sharma, Amit and Khan, Mohammad Azhar and Pratap, Rameshwar and Kang, Keegan}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {6178--6203}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/sharma26b/sharma26b.pdf}, url = {https://proceedings.mlr.press/v337/sharma26b.html}, abstract = {$\texttt{{TensorSketch}}$ by [Pham and Pagh, 2013, Kar and Karnick, 2012] provides efficient sketching algorithms for high-dimensional polynomial kernels $\mathbf{x}^{\otimes p} \in \mathbb{R}^{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 $\texttt{CountSketch}$ [Charikar et al., 2004] algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\operatorname{nnz}(\mathbf{x}) + D \log D)\big)$. 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 $\texttt{{TensorSketch}}$ [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.} }
Endnote
%0 Conference Paper %T Improving TensorSketch Using Complex Random Variables %A Amit Sharma %A Mohammad Azhar Khan %A Rameshwar Pratap %A Keegan Kang %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-sharma26b %I PMLR %P 6178--6203 %U https://proceedings.mlr.press/v337/sharma26b.html %V 337 %X $\texttt{{TensorSketch}}$ by [Pham and Pagh, 2013, Kar and Karnick, 2012] provides efficient sketching algorithms for high-dimensional polynomial kernels $\mathbf{x}^{\otimes p} \in \mathbb{R}^{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 $\texttt{CountSketch}$ [Charikar et al., 2004] algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\operatorname{nnz}(\mathbf{x}) + D \log D)\big)$. 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 $\texttt{{TensorSketch}}$ [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.
APA
Sharma, A., Khan, M.A., Pratap, R. & Kang, K.. (2026). Improving TensorSketch Using Complex Random Variables. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:6178-6203 Available from https://proceedings.mlr.press/v337/sharma26b.html.

Related Material