Tensor Sketch¶
A randomized linear embedding for tensor-product features that combines factorwise CountSketches by convolution, approximating inner products or norms without materializing the full Kronecker vector.
Core Idea¶
Tensor Sketch is a randomized linear map that compresses a tensor-product or Kronecker-product feature vector without explicitly forming its enormous ambient representation. Each factor is hashed with a CountSketch-like map; the sketches are combined by circular convolution, implemented efficiently through the fast Fourier transform. The result approximates inner products and norms of polynomial-feature tensors in a much smaller dimension.
The identity is more specific than “sketch a tensor.” It requires a product-aware random embedding whose hash and sign structure makes the sketch of a tensor product computable from factor sketches. For two factors, convolution replaces enumeration of every coordinate pair. For a degree-p polynomial kernel, the resulting explicit feature map approximates (x^T y)^p while avoiding the d^p monomial vector.
Scope of Application¶
The method originated as an explicit randomized feature map for polynomial kernels. It is also used in kernel regression, canonical correlation, low-rank approximation of tensor-structured data, bilinear pooling, Kronecker-product regression, and randomized numerical linear algebra. The literal role package survives: product-structured feature, compact random map, fast factorwise computation, and norm or subspace preservation.
Scope depends on the guarantee. Approximation of one inner product, preservation of a fixed set, and subspace embedding are progressively stronger demands and may require different sketch dimensions. The dossier does not treat one parameter bound as universal across degree, failure probability, leverage, or application.
Clarity¶
For factor vectors x and y, a CountSketch assigns each coordinate a bucket and sign. Tensor Sketch assigns the product coordinate (i,j) to bucket (h1(i)+h2(j)) mod m with sign s1(i)*s2(j). Consequently, the sketch of x⊗y is the circular convolution of the factor sketches. FFT multiplication computes this convolution without visiting all d1*d2 product coordinates.
Manages Complexity¶
Polynomial and interaction features expand combinatorially with degree. Tensor Sketch compresses that feature space into m coordinates and computes the embedding from factors in roughly factor-reading plus FFT time rather than product-dimension time. This permits linear algorithms in the sketch space to approximate nonlinear kernel operations.
Abstract Reasoning¶
The hash rules imply that each output bucket aggregates signed product coordinates whose factor buckets sum to that index. Independence and zero-mean sign cancellation make inner-product estimators unbiased or controlled under the construction's assumptions. Variance bounds then determine a dimension sufficient for a requested failure probability.
Knowledge Transfer¶
The literal mechanism transfers from degree-two bilinear features to higher polynomial degrees, Kronecker design matrices, tensor regression, and structured matrix products. Hash addition, sign multiplication, convolution, and randomized geometry remain.
The broad principle “compute on a compressed interaction representation” transfers farther, but that is Dimensionality Reduction or Compression. A feature hash, random Fourier feature map, or low-rank tensor factorization is not Tensor Sketch merely because it makes a large problem smaller.
Relationships to Other Abstractions¶
Current abstraction Tensor Sketch Domain-specific
Parents (1) — more general patterns this builds on
-
Tensor Sketch is a kind of Dimensionality Reduction Prime
Tensor Sketch is a strict specialization of
prime:dimensionality_reduction, the minimal proposed parent.
Hierarchy paths (4) — routes to 3 parentless roots
- Tensor Sketch → Dimensionality Reduction → Approximation → Representation → Abstraction
- Tensor Sketch → Dimensionality Reduction → Compression → Abstraction
- Tensor Sketch → Dimensionality Reduction → Compression → Optimization
- Tensor Sketch → Dimensionality Reduction → Compression → Aggregation → Micro Macro Linkage
Neighborhood in Abstraction Space¶
Tensor Sketch sits in a sparse region of the domain-specific corpus (80th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Applied Linear & Special Functions (18 abstractions)
Nearest neighbors
- Compact Operator — 0.83
- Algebraic stack — 0.82
- Fredholm Kernel — 0.82
- Hausdorff Space — 0.82
- Variable Elimination — 0.81
Computed from structural-signature embeddings · 2026-09-08