# Improved Sparse Recovery for Approximate Matrix Multiplication

Preprint · Yahel Uffenheimer, Omri Weinstein

- Archive id: arxiv:2602.04386
- Published: 2026-02-04
- arXiv: https://arxiv.org/abs/2602.04386
- Source URL: https://arxiv.org/abs/2602.04386
- PDF: https://arxiv.org/pdf/2602.04386
- Provenance: arxiv

## Abstract

We present a simple randomized algorithm for approximate matrix multiplication (AMM) whose error scales with the \*output\* norm $\\\|AB\\\|\_F$. Given any $n\\times n$ matrices $A,B$ and a runtime parameter $r\\leq n$, the algorithm produces in $O(n^2(r+\\log n))$ time, a matrix $C$ with total squared error $\\mathbb{E}\[\\\|C-AB\\\|\_F^2\]\\le (1-\\frac{r}{n})\\\|AB\\\|\_F^2$, per-entry variance $\\\|AB\\\|\_F^2/n^2$ and bias $\\mathbb{E}\[C\]=\\frac{r}{n}AB$. Alternatively, the algorithm can compute an \*unbiased\* estimation with expected total squared error $\\frac{n}{r}\\\|{AB}\\\|\_{F}^2$, recovering the state-of-art AMM error obtained by Pagh's TensorSketch algorithm (Pagh, 2013). Our algorithm is a log-factor faster. The key insight in the algorithm is a new variation of pseudo-random rotation of the input matrices (a Fast Hadamard Transform with asymmetric diagonal scaling), which redistributes the Frobenius norm of the \*output\* $AB$ uniformly across its entries.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.