{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia5yndt6hkp7yldocenpm6jxsgbjpw77tmdnpekifgipjsvetpzsq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnz63opwoms2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.12179v1",
  "publishedAt": "2026-06-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Christoper Musco",
    "Indu Ramesh"
  ],
  "textContent": "**Authors:** Christoper Musco, Indu Ramesh\n\nA large body of work studies the problem of learning an approximation to an implicit matrix $A\\in \\mathbb{R}^{m\\times n}$ that is only accessible implicitly via matrix-vector product queries (matvec queries) of the form ${x} \\rightarrow {A}{x}$ or ${x} \\rightarrow {A}^T{x}$. Of particular interest are methods that learn a near-optimal approximation with a fixed sparsity pattern. For example, we might want to learn a near-optimal diagonal, banded, or arrow-head approximation to an implicit matrix $A$. Naturally, the number of matvec queries required to solve this problem depends on the sparsity pattern, which can be encoded as a binary matrix ${S}\\in \\\\{0,1\\\\}^{m\\times n}$. The query complexity of previous algorithms scales with quantities like the total number of ones in ${S}$, its maximum column/row sparsity, or the chromatic number of a its \"conflict graph\". These quantities are incomparable: for a given ${S}$, parameterizing by one might yield lower query complexity than another. In this work, we unify and tighten these prior results by providing a nearly sharp characterization of the matvec query complexity of sparse matrix approximation. Generalizing a definition from graph algorithms, let the degeneracy, ${degen}({S})$, denote the smallest number $k$ so that, if we iteratively delete all rows and columns of ${S}$ with $\\leq k$ ones, we are left with an empty matrix. We show that a near-optimal approximation to $A$ with sparsity pattern $S$ can be learned with $\\tilde{O}({degen}({S}))$ matrix-vector product queries, and $Ω({degen}({S}))$ queries are necessary, for any sparsity pattern ${S}$. Moreover, unlike prior work based on graph coloring, all of our methods run in polynomial time.",
  "title": "Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products"
}