Research map / Learning theory and algorithms / Sample complexity
Optimal Sketching for Trace Estimation
Shuli Jiang, Hai Pham, David Woodruff, Qiuyi Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Hutch++ or NA-Hutch++ instead of Hutchinson | Hutchinson · synthetic, roget, arxiv_cm, precipitation | failed estimates over 100 trials | Improved |
| use adaptive Hutch++ instead of non-adaptive NA-Hutch++ | NA-Hutch++ · four datasets | failed estimates | Improved |
| use non-adaptive NA-Hutch++ instead of adaptive Hutch++ in parallel execution | Hutch++ · four datasets | parallel wall-clock time | Improved |
| compare NA-Hutch++ with Hutch++ and Hutchinson in sequential execution | Hutch++ · four datasets | sequential wall-clock time | No clear effect |
| compare NA-Hutch++ with Hutchinson in parallel execution | Hutchinson · four datasets | parallel wall-clock time | No clear effect |
| use Hutch++ trace estimation in max-entropy log determinant estimation | Hutchinson · bcsstk20, bcsstm08 | log determinant estimate | Improved |
| apply to non-PSD matrix A^3 | NA-Hutch++ · arxiv_cm triangle counting | failed estimates | No clear effect |
Closest papers by meaning
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.86)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.84)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.84)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.83)
- Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning (NeurIPS 2024 · similarity 0.82)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.82)
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.
