📊 statistics

Improving TensorSketch Using Complex Random Variables

This paper introduces a novel variant of the TensorSketch algorithm that leverages complex random variables to achieve a superior variance bound of $2^p/D$ for high-dimensional polynomial kernels while maintaining the efficient input-sparsity running time of the original method.

Original authors: Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang

Published 2026-08-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive jigsaw puzzle, but instead of pieces, you have millions of numbers representing data points. In the world of machine learning, computers often need to find patterns by comparing these numbers. Sometimes, the patterns are simple, like a straight line. But often, the world is messy and curved, so computers use "kernels"—mathematical magic tricks that let them see complex, curved relationships between data points. One popular trick is the "polynomial kernel," which looks at how features interact when multiplied together many times.

The problem is that as you multiply these features together more and more times (raising them to a higher "degree"), the number of pieces in your puzzle explodes. It grows so fast that even the fastest supercomputers would get stuck trying to calculate every single piece. To fix this, scientists invented "sketching." Think of sketching like taking a high-resolution photo and compressing it into a tiny thumbnail. You lose some detail, but you keep the most important shapes and colors, and you can process the thumbnail instantly. For years, the best way to do this for polynomial puzzles was a method called TensorSketch. It was fast, but it had a flaw: as the puzzle got more complex, the "thumbnail" became a bit fuzzy, and the computer's guess started to wobble with more error.

Recently, a team of researchers asked a curious question: What if we stopped using just regular numbers and started using "complex" numbers—numbers that include an imaginary part, like the square root of negative one? They wondered if this imaginary twist could make the thumbnail sharper. A previous study showed that for one type of sketching, using complex numbers did make the picture clearer (reducing the fuzziness). However, that method was slow and clunky, like trying to carry a heavy backpack while running. The researchers in this paper wanted to know: Can we get that super-sharp, complex-number clarity without the heavy backpack? Can we make the fast, lightweight TensorSketch method just as good as the slow, heavy one?

The paper, titled "Improving TensorSketch Using Complex Random Variables," says yes. The authors, Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, and Keegan Kang, have built a new version of TensorSketch that uses these complex numbers but keeps the speed of the original. They didn't just guess; they proved it with math and tested it with real data.

Here is how they did it. The original TensorSketch works by taking your data, mixing it up with random signs (like flipping a coin to decide if a number is positive or negative), and then squishing it down. The new method, which they call "Complex-to-Real TensorSketch" (or CtR TensorSketch), changes the coin flip. Instead of just heads or tails (1 or -1), they use a four-sided die that lands on 1, -1, or two imaginary numbers (i and -i). This might sound like it would make the result a weird, imaginary mess, but they have a clever trick. They take the result, which is a complex number, and split it into two parts: the "real" part and the "imaginary" part. Then, they stick these two parts side-by-side to form a new, real-world vector.

The magic happens because of how these imaginary numbers interact. When the researchers crunched the numbers, they found that the "fuzziness" (or variance) of their new method grew much slower than the old one. In the old method, the error grew like $3^p$ (where $p$ is the complexity of the puzzle). In their new method, the error only grows like $2^p$ . That might sound like a small difference, but in the world of exponential growth, it's a massive improvement. It means for complex puzzles, their new sketch is significantly more accurate.

Crucially, they proved that this new method is still just as fast as the old one. While other methods that use complex numbers require the computer to do heavy, slow calculations (taking time proportional to the full size of the data), their method stays "input-sparse." This means it only spends time on the parts of the data that actually exist, ignoring the zeros. They showed that the time it takes to run their algorithm is $O(p(nnz(x) + D \log D))$ , which is the same speed as the original TensorSketch.

To make sure this wasn't just a math trick that worked on paper, they ran experiments. They tested their method on synthetic data (made-up numbers) and real-world datasets like the MAGIC Gamma Telescope data and COD-RNA. They compared their CtR TensorSketch against the standard TensorSketch and other complex methods. The results were clear: their new method produced much more accurate approximations (measured by something called KL divergence, which checks how similar the sketch is to the original) while taking the same amount of time to compute. In fact, in some tests, their method was even faster than the other complex methods because it didn't have to do the heavy lifting.

The paper also addresses a potential confusion. They showed that simply using complex numbers in a different type of sketch (called CountSketch) doesn't automatically make it better. The improvement only comes from the specific way they combined the complex numbers with the TensorSketch structure. This proves that their result isn't a fluke; it's a specific, non-trivial improvement that comes from the way the math cancels out certain error terms.

In short, this paper takes a fast but slightly fuzzy tool (TensorSketch), upgrades it with a bit of imaginary math to make it sharper, and ensures it stays fast. It's like taking a quick sketch artist and giving them a special set of colored pencils that let them capture more detail without slowing down their hand. For anyone building machine learning models that need to understand complex relationships in huge datasets, this new method offers a way to get better answers without waiting longer for the computer to finish its work.

Technical Summary: Improving TensorSketch Using Complex Random Variables

Problem Statement
Polynomial kernels, defined as $k(x, y) = \langle x, y \rangle^p$ , are essential for modeling higher-order non-linear interactions in machine learning. However, explicitly computing the inner product of the $p$ -fold Kronecker product $x^{\otimes p} \in \mathbb{R}^{d^p}$ is computationally infeasible due to exponential dimension growth. Randomized sketching techniques, such as TensorSketch (Pham and Pagh [2013]) and JL-type random feature maps (Kar and Karnick [2012]), approximate these kernels efficiently. While TensorSketch offers input-sparsity running time $O(p(\text{nnz}(x) + D \log D))$ suitable for high-dimensional sparse data, both it and JL-type methods suffer from variance that grows exponentially with the polynomial degree $p$ , scaling as $3^p/D$ .

Recent work by Wacker et al. [2023] demonstrated that using complex-valued random variables in JL-type projections could reduce this variance dependence to $2^p/D$ . However, their method relies on dense matrix multiplications with cost $O(pDd)$, rendering it inefficient for high-dimensional sparse inputs. Furthermore, their approach did not extend to the hashing-based TensorSketch framework.

Methodology
This paper introduces a Complex-to-Real (CtR) variant of TensorSketch that bridges the gap between variance reduction and computational efficiency. The core methodology involves three key components:

Complex CountSketch: The authors define a Complex CountSketch mapping where the random sign function $s: [d] \to \{1, \omega, \omega^2, \omega^3\}$ draws values uniformly from the four fourth roots of unity ( $\omega = i$ ), rather than the standard real Rademacher signs $\{-1, 1\}$ .
Complex TensorSketch Construction: They extend this to degree- $p$ kernels by constructing $p$ independent Complex CountSketch mappings and combining them via FFT-based convolution. This allows the sketch of $x^{\otimes p}$ to be computed implicitly without forming the full tensor, preserving the input-sparsity time complexity.
Complex-to-Real (CtR) Conversion: To ensure the output is compatible with standard real-valued machine learning algorithms, the authors apply a CtR transformation. This involves concatenating the real and imaginary parts of the complex sketch vector $\Phi_C(x^{\otimes p}) \in \mathbb{C}^{D/2}$ to form a real-valued vector $\Phi_{CtR}(x^{\otimes p}) \in \mathbb{R}^D$ .

Theoretical Guarantees
The paper provides rigorous theoretical analysis proving that the proposed estimator is unbiased for the polynomial kernel $\langle x, y \rangle^p$ . Crucially, the variance analysis leverages the properties of the fourth roots of unity and Khintchine-type inequalities adapted for complex variables. The authors prove that the variance of the CtR TensorSketch estimator satisfies:
$\text{Var}(\hat{k}_{CtR}(x, y)) \leq \frac{2^{p+1} - 2}{D} \|x\|_2^{2p} \|y\|_2^{2p}$
This represents a significant improvement over the classical TensorSketch variance bound of $\frac{3^p - 1}{D} \|x\|_2^{2p} \|y\|_2^{2p}$ , reducing the exponential base from $3$ to $2$. The time complexity remains $O(p(\text{nnz}(x) + D \log D))$ , matching the efficiency of the original real-valued TensorSketch.

Experimental Results
The authors validate their method on both synthetic and real-world datasets (MAGIC Gamma Telescope, COD-RNA) against standard TensorSketch, JL-type sketches (Gaussian and Rademacher), and their CtR variants.

Accuracy: Measured via KL divergence between the exact kernel and the sketch-based approximation, the CtR TensorSketch consistently achieves the lowest error across various polynomial degrees ( $p$ ) and sketch dimensions ( $D$ ).
Efficiency: In terms of wall-clock construction time, the proposed method retains the input-sparsity advantage, performing comparably to real TensorSketch and significantly faster than dense JL-type methods, which scale with $O(pDd)$.
Downstream Tasks: Experiments on binary classification using Linear SVMs show that CtR TensorSketch achieves higher accuracy than real TensorSketch and dense JL variants while maintaining the fastest total execution time (compression + training).

Significance and Claims
The paper claims that this work is the first to successfully adapt the Complex-to-Real framework to the hashing-based CountSketch/TensorSketch paradigm. Unlike prior complex-valued approaches that were limited to dense projections, this method achieves improved variance bounds ( $2^p$ vs $3^p$ ) while retaining the critical input-sparsity running time required for high-dimensional sparse data.

The authors note that the variance reduction is non-trivial; simply applying complex variables to CountSketch without the specific CtR construction and analysis of cross-terms does not yield variance reduction. The improvement stems from the vanishing of specific cross terms in the variance analysis due to the properties of the fourth roots of unity.

The paper concludes by identifying two open directions: investigating whether higher-order roots of unity could yield even tighter approximation guarantees, and exploring the extension of CtR constructions to other kernel families beyond polynomial kernels. The work positions CtR TensorSketch as a promising alternative for applications requiring efficient polynomial kernel approximation, including linear SVM training, deep learning scalability, and fine-grained visual recognition.

Technical Summary: Improving TensorSketch Using Complex Random Variables

More like this