Research map / Learning theory and algorithms / Matrix and tensor methods
Randomized sketching for matrices
Uses random projections and frequent-directions sketches for fast approximate linear algebra.
96 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Matrix and tensor methods, keyword cluster “matrices · matrix completion · rank matrix”
State History Tried Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
21 papers in 2023–24 and 15 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 12.1% to 8.1%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Efficient Temporal Sequence Comparison and Classification Using Gram Matrix Embeddings on a Riemannian Manifold (CVPR 2016 · 85 citations)
- 2017 · Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (NeurIPS 2017 · 382 citations)
- 2018 · Randomized Clustered Nystrom for Large-Scale Kernel Machines (AAAI 2018 · 18 citations)
- 2019 · Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (ICML 2019 · 42 citations)
- 2020 · Coded Sequential Matrix Multiplication For Straggler Mitigation (NeurIPS 2020 · 9 citations)
- 2021 · Approximate Multiplication of Sparse Matrices with Limited Space (AAAI 2021 · 4 citations)
- 2022 · DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization (NeurIPS 2022 · 26 citations)
- 2023 · Efficient Second-Order Plane Adjustment (CVPR 2023 · 5 citations)
- 2024 · Robust Self-calibration of Focal Lengths from the Fundamental Matrix (CVPR 2024 · 3 citations)
- 2025 · Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · 1 citation)
- 2026 · Dataless Weight Disentanglement in Task Arithmetic via Kronecker-Factored Approximate Curvature (ICLR 2026 · 0 citations)
Earliest papers here
- Efficient Temporal Sequence Comparison and Classification Using Gram Matrix Embeddings on a Riemannian Manifold (CVPR 2016 · 85 citations)
- Normalized Spectral Map Synchronization (NeurIPS 2016 · 35 citations)
- Binary embeddings with structured hashed projections (ICML 2016 · 24 citations)
What has been tried
85 papers here report 655 measured changes (a component added, removed or swapped, compared with a baseline): helped 70%, no clear effect 10%, hurt 15%, mixed 5%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| add real focal length checking within RANSAC | Phototourism · mAAf (0.1) | 23.95 -> 24.23 | Helped | Robust Self-calibration of Focal Lengths from the Fundamental Matrix (CVPR 2024 · 3 citations) |
| Use four constraints C4 instead of three pairwise constraints C3 | Three-view synthetic correspondences, σ = 1px / 5px / 10px · AUC@1px | 0.998 / 0.961 / 0.882 -> 0.765 / 0.481 / 0.353 | Hurt | Revisiting Sampson Approximations for Geometric Estimation Problems (CVPR 2024 · 2 citations) |
| Replace storing A^T A with a sampled, reweighted row sketch | Sketched regression · Sketch size | O(d^2 + ds/\epsilon) -> O(ds/\epsilon) | Helped | Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · 1 citation) |
| Increase latent dimension from 3 to 10 | Prediction performance · NMSE | 95.28% -> 88.33% | Helped | MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product (ICML 2025 · 0 citations) |
| Initialize SGA with ColRand instead of PCA | MinCostFlow, GROW7, SC205, and SCAGR25 · objective ratio | Hurt | Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming (NeurIPS 2024 · 0 citations) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 36 papers; from OpenAlex and the papers' affiliations).
- Carnegie Mellon University · 4 papers
- University of California, Berkeley · 3 papers
- Toyota Technological Institute at Chicago · 2 papers
- Adobe · 2 papers
- Columbia University · 2 papers
- Microsoft · 2 papers
- Rutgers University · 2 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Low-rank approximation theory (142 papers)
- Matrix completion and factorization (118 papers)
- Structured low-rank learning (87 papers)
- Geometry of low-rank and SPD structure (71 papers)
Elsewhere in the topic
- Nonconvex low-rank and sparse optimization (112 papers)
- Sparse regression with guarantees (94 papers)
- High-dimensional estimation theory (89 papers)
- Signal recovery and phase retrieval (66 papers)
- Sparse and robust PCA (66 papers)
- Tensor network decompositions (45 papers)
- Low-rank tensor completion (45 papers)
- Randomized tensor decomposition algorithms (43 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).