Research map / Learning theory and algorithms / Matrix and tensor methods
Fast Sampling-Based Sketches for Tensors
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces p-samples built from random permutations and FFT-based fast convolution so that ℓ0 samplers and ℓ1 embeddings can be applied to rank-one 2- and 3-mode tensors in near-linear time in d.
Problem
Fast application of sampling-based linear sketches (ℓ0 sampling and ℓ1 embeddings) to low-rank (rank-one) tensors, where naive application requires expanding to d^2 or d^3 entries.
Approach
Construct pairwise-near-independent subsets ("p-samples") of tensor entries that admit fast summation via convolution (FFT) and Toeplitz-like multiplication, after randomly permuting indices per mode; combine with random sign flips per mode to get ℓ0 samplers and ℓ1 embeddings for rank-one 2- and 3-mode tensors.
Key results
- ℓ0 sampler on rank-one 2-mode tensors runs in O(mn) time and on 3-mode tensors in O(mn log^2 n) time, with sketch dimension O(log(1/δ) log^2 n (log log n + log(1/δ))).
- ℓ1 embedding with O(1) distortion uses sketch dimension O(log^4 n + log^2(1/δ) log n) and applies to rank-one 3-mode tensors in O(mk log^2 k) time.
- Experiments on 40x40x40 synthetic supports show the ℓ0 sampler's output fractions closely match uniform-sampling expectations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed p-sample construction with fast summation | Rank-one 2-mode tensors · ℓ0 sampling | application time: O(m n) | Helped |
| Use the proposed p-sample construction with fast summation | Rank-one 3-mode tensors · ℓ0 sampling | application time: O(m n\log^2 n) | Helped |
| Use the proposed p-sample construction with fast summation | Rank-one 2-mode tensors · ℓ1 embedding | application time: O(m k) | Helped |
| Use the proposed p-sample construction with fast summation | Rank-one 3-mode tensors · ℓ1 embedding | application time: O(m k\log^2 k) | Helped |
| Use the proposed ℓ0 sampler | 3-mode tensors with disjoint-rectangle support · ℓ0 sampling, disjoint rectangles | fraction sampled from first rectangle: 0.9650 vs 0.9524 | No clear effect |
| Use the proposed ℓ0 sampler | 3-mode tensors with a rectangle plus an equal-size random support · ℓ0 sampling, rectangle (1, 1, 1) | fraction sampled from rectangle: 0.47 | No clear effect |
Surprising findings
- Kronecker-structured sketches cannot match the ℓ1 embedding bounds for a single vector (poly(n) dimension lower bound), so the proposed approach is needed.
Limitations
- Only handles 2- and 3-mode tensors; extension to four modes is an open problem.
- Sketch construction time per entry is still O(n), not O(1) as in CountSketch.
- Experiments assume a perfect singleton tester rather than a practical one.
Experimental setup
Datasets: synthetic tensors (40x40x40 with rectangle and random supports)
Benchmarks: synthetic 40x40x40 tensor supports
Metrics: fraction of samples in first rectangle vs expected uniform f failure counts
Baselines: dense Gaussian sketch Kronecker-structured sketches rectangle sampling
Builds on: CountSketch tensor sketching Indyk l1 embedding / Cauchy sketches l0 sampling standard recipe
Closest papers by meaning
- Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels (NeurIPS 2019 · similarity 0.87)
- Adaptive Sketching for Fast and Convergent Canonical Polyadic Decomposition (ICML 2020 · similarity 0.87)
- Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time (ICML 2022 · similarity 0.87)
- Sublinear Time Orthogonal Tensor Decomposition (NeurIPS 2016 · similarity 0.86)
- Convolutions and More as Einsum: A Tensor Network Perspective with Advances for Second-Order Methods (NeurIPS 2024 · similarity 0.85)
- Efficient Leverage Score Sampling for Tensor Train Decomposition (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.