{"id":"arxiv/2606.12179","url":"https://arxiv.org/abs/2606.12179","tags":["cs.DS","math.NA"],"score":0,"title":"Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products","domain":"cs.DS","source":"arxiv","authors":["Christoper Musco","Indu Ramesh"],"reviews":0,"subject":"cs.DS","summary":"A 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}