{
  "$type": "site.standard.document",
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.04386v1",
  "publishedAt": "2026-02-05T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Yahel Uffenheimer",
    "Omri Weinstein"
  ],
  "textContent": "**Authors:** Yahel Uffenheimer, Omri Weinstein\n\nWe 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.",
  "title": "Improved Sparse Recovery for Approximate Matrix Multiplication"
}