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.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2945
Origin domain: randomized numerical linear algebra
Subdomain: sketching algorithms
Aliases: TensorSketch

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.^[1]^[2]

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.^[1]

Structural Signature¶

Recognition roles:

factor vectors or tensor-structured input whose explicit Kronecker product is prohibitively large;
target sketch dimension much smaller than the ambient product dimension;
independent hash maps and random signs for factor coordinates;
product hash rule adding bucket indices modulo the sketch dimension;
product sign rule multiplying factor signs;
convolution/FFT implementation combining factor sketches;
randomized fidelity contract for inner products, norms, or an entire subspace; and
downstream computation performed in the compressed feature space.

A generic random projection of a materialized tensor does not satisfy the computational role. A factorwise map with no justified product combination does not satisfy the fidelity role.

What It Is Not¶

Tensor Sketch is not a tensor decomposition such as CP, Tucker, or tensor train: those seek low-rank factors for a tensor already represented or accessed, while Tensor Sketch supplies a randomized embedding. It is not CountSketch alone; CountSketch is the base sparse hashing mechanism, while the tensor construction couples factor hashes through convolution. It is not the Johnson–Lindenstrauss lemma itself, which is a dimension-preservation guarantee applicable to a broader family of embeddings.

Nor is every method called “tensor random projection” TensorSketch. Dense Kronecker random matrices, Tensor Random Projection, and recursive sketches may share objectives but differ in distribution, computation, and guarantees. The name should be tied to the convolutional CountSketch construction or a clearly identified extension.^[2]

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.^[2]^[3]

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.

This equality is exact for the chosen random map; approximation enters when the compact sketch is used to estimate inner products or norms. Separating computational identity from probabilistic error prevents a common confusion: FFT roundoff aside, convolution is not the approximation. Hash collisions in the reduced dimension create the randomized estimator's variance.

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.^[1]

The compression retains only the geometry promised by the selected theorem. Individual tensor coordinates cannot generally be reconstructed. Collisions couple estimates; higher degree can worsen variance; and using too small a sketch silently destroys fidelity. The abstraction manages computational complexity by accepting controlled randomized information loss.

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.^[1]^[2]

Linearity permits sketches of sums to be accumulated without returning to the ambient tensor space. A subspace-embedding guarantee permits approximate least squares or low-rank computation for every vector in a fixed subspace, not only for one query. But a pointwise guarantee cannot be promoted to uniform preservation after adaptively choosing a query from the sketch.

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.

Examples¶

Degree-two polynomial features. Instead of materializing all pairwise products x_i*x_j, sketch two copies of x, convolve their bucket arrays, and use the result as an explicit feature vector. Dot products of such sketches estimate the squared ordinary inner product.^[1]

Bilinear feature. For distinct vectors x and y, the algorithm sketches x⊗y from the two factor sketches. This supports compact bilinear pooling while retaining interaction information unavailable from simply adding the factors.

Subspace embedding. A Kronecker-structured regression matrix can be sketched without expanding every product column. If the selected TensorSketch dimension meets a subspace theorem, least-squares geometry is preserved for all coefficient vectors in that fixed subspace.^[2]

Nonexample—CP decomposition. Approximating a tensor by a sum of rank-one tensors changes representation through low rank; it does not use CountSketch convolution or the same randomized norm contract.

Repeated-sketch confidence control. If one sketch is too variable for a scalar kernel estimate, independent repetitions can be aggregated or their estimates averaged. The repetitions must use independently documented hash/sign families, and the resulting error statement must be derived for that aggregation. Merely rerunning an identical seeded sketch produces identical collisions and supplies no new concentration. This worked boundary links the randomness role to a testable implementation decision rather than treating “randomized” as a decorative label.

Structural Tensions¶

Speed versus variance. Smaller sketches compute faster but suffer more collisions. Diagnostic: report the target distortion/failure probability and verify the dimension theorem for the actual degree.
Pointwise versus uniform guarantee. Preserving one vector is weaker than preserving a subspace. Diagnostic: identify whether queries were fixed before randomness or selected adaptively afterward.
Product exploitation versus materialization. The method's advantage disappears if the tensor is first expanded. Diagnostic: trace the implementation and confirm factorwise sketches feed convolution directly.
Reproducibility versus independence. Fixed seeds aid replay but reused hashes can invalidate an independence proof. Diagnostic: inventory which factors, repetitions, and trials share random maps.
Autonomy versus Dimensionality Reduction. Random projection and Tensor supply ingredients. Diagnostic: remove additive hash composition and FFT convolution; if tensor-product computation no longer follows, Tensor Sketch retains an autonomous residual.

Structural–Framed Character¶

The hash/convolution construction is structural; sketch dimension, random independence, degree, and guarantee are problem-framed. Application papers may emphasize kernel approximation or tensor regression, but the same mechanism remains recognizable. Performance claims are meaningful only relative to sparsity, factor dimensions, and desired fidelity.

Structural Core vs. Domain Accent¶

The portable core is randomized compression that preserves selected geometry. The domain accent supplies Kronecker products, polynomial features, CountSketch hashing, random signs, convolution, FFT, variance, and subspace embeddings. Those terms are indispensable.

The candidate is domain-specific. prime:dimensionality_reduction captures the broader high-to-low representation objective; Tensor Sketch supplies one specialist construction optimized for product structure.

Tensor Sketch is a strict specialization of prime:dimensionality_reduction, the minimal proposed parent. It also relates to Randomness, Compression, Approximation, and Algorithm. Tensor and Tensor Representation are domain neighbors describing the substrate rather than the reduction procedure.

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

Show alternative paths (3)

Neighborhood in Abstraction Space¶

Tensor Sketch sits in a sparse region of the domain-specific corpus (80^th 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

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

CountSketch: base sparse hashing map without the tensor-product convolution rule.
Feature hashing: generic coordinate hashing, often without product-aware composition.
Random projection: broader embedding family.
Tensor decomposition: low-rank structural representation rather than randomized sketch.
Tensor Random Projection: related but distributionally different product embedding family.
Polynomial kernel: target similarity function; Tensor Sketch is an approximate explicit map.
Fast Fourier transform: computational primitive used for convolution, not the abstraction itself.

References¶

[1] Ninh Pham and Rasmus Pagh, “Fast and Scalable Polynomial Kernels via Explicit Feature Maps,” Proceedings of KDD 2013, 239–247, https://doi.org/10.1145/2487575.2487591. registry ↩a ↩b ↩c ↩d ↩e

[2] Haim Avron, Huy L. Nguyen, and David P. Woodruff, “Subspace Embeddings for the Polynomial Kernel,” Advances in Neural Information Processing Systems 27 (2014), https://proceedings.neurips.cc/paper_files/paper/2014/hash/ad178e96136f045bbb98ea3d76e25e6c-Abstract.html. registry ↩a ↩b ↩c ↩d ↩e

[3] Rasmus Pagh, “Compressed Matrix Multiplication,” ACM Transactions on Computation Theory 5.3 (2013), Article 9, https://doi.org/10.1145/2493252.2493254. registry ↩