Research map / Learning theory and algorithms / Matrix and tensor methods
Matrix Product Sketching via Coordinated Sampling
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.
Proposes coordinated (priority) sampling sketches for approximate matrix products A^T B computed independently for A and B, giving sketch sizes O(s/ε²) for s-sparse rows, beating linear sketches on sparse data.
Problem
Approximating the matrix product A^T B from independently computed small sketches of A and B (shared random seed only), which linear sketches handle at size O(d/ε²) and which importance-sampling methods cannot compute in this setting.
Approach
Uses coordinated random sampling (Priority Sampling with a shared hash) so that row samples of A and B overlap on indices where both row norms are large; the sampling probability is effectively the minimum of the two normalized squared row norms, which gives a bound matching norm-based importance sampling without needing both matrices. Extends to sketched least-squares regression with leverage-sco
Key results
- Priority sampling matches JL sketch on dense synthetic matrices and outperforms it as sparsity increases (10%, 40%, 80% non-zeros).
- Theory: expected squared Frobenius error at most 2/(k-1) ||A||_F^2 ||B||_F^2 with sketches of k rows, matching the sampling guarantee up to constants.
- Paper reports an order-of-magnitude improvement over linear sketching on sampling-based experiments (abstract claim); for 2% sparse rows, about 50x space savings claimed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use coordinated Priority Sampling instead of linear sketching for sparse matrix products | Matrix product sketching · Synthetic matrix multiplication and real-world applications | Sketch compactness: 50x savings | Helped |
| Use coordinated sampling instead of linear sketching | Matrix product sketching · Matrix multiplication applications | Sketch size: order of magnitude improvement | Helped |
| Use sampling-based sketches instead of JL sketches as matrix sparsity increases | Matrix product sketching · Synthetic data with varying sparsity | Approximation error | Helped |
| Use sampling-based regression sketches instead of linear sketches as matrices become sparser | Sketched regression · IMDB and Android Review datasets | Approximation error | Helped |
| Use Priority Sampling instead of linear sketching for dense matrices | Matrix product sketching · Synthetic matrix multiplication | Approximation error | No clear effect |
| Use Priority Sampling rather than Threshold Sampling | Matrix product sketching · Matrix product approximation | Expected squared Frobenius error: \frac{2}{k-1} ... vs. \frac{2}{k} ... | Hurt |
| Replace storing A^T A with a sampled, reweighted row sketch (ablation) | Priority Sampling regression · Sketched regression | Sketch size: O(d^2 + ds/\epsilon) -> O(ds/\epsilon) | Helped |
Surprising findings
- Sampling with probabilities proportional to the minimum of the two normalized row norms suffices for the same guarantee as the product-based importance sampling.
Limitations
- Sketches must store row indices, adding overhead that is offset only when matrices are sparse.
- Regression sketch of size O(d/ε) only with additive error ε||b||², not the stronger residual guarantee.
- Experiments on the LLM attention task are limited to approximating Q K^T for KV cache.
Experimental setup
Datasets: synthetic Gaussian matrices with outliers Android application reviews IMDB movie reviews LongBench MultiFieldQA
Benchmarks: synthetic matrix multiplication IMDB regression Android review regression LongBench MultiFieldQA KV cache
Metrics: normalized Frobenius error relative regression error sketch size
Baselines: JL sketch CountSketch
Builds on: Priority Sampling Subsampled randomized matrix multiplication Johnson-Lindenstrauss projection CountSketch SPLADE
Closest papers by meaning
- Precise expressions for random projections: Low-rank approximation and randomized Newton (NeurIPS 2020 · similarity 0.90)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.89)
- Learning the Positions in CountSketch (ICLR 2023 · similarity 0.89)
- Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform (NeurIPS 2020 · similarity 0.88)
- Sketching Algorithms and Lower Bounds for Ridge Regression (ICML 2022 · similarity 0.88)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.88)
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.