# Fixed-sparsity matrix approximation from matrix-vector products

arXiv: https://arxiv.org/abs/2402.09379 · HTML: https://mlsanity.com/paper/2402.09379/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2024.

## Built on by (most cited first, 3 of 3)

- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [Truncated automatic sparse differentiation for machine learning interatomic potentials](https://mlsanity.com/paper/2609.20510/) (2026)

## Abstract (arXiv)

We study the problem of approximating a matrix A with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when A is accessed only by matrix-vector products. We describe a simple randomized algorithm that returns an approximation with the given sparsity pattern with Frobenius-norm error at most (1+varepsilon) times the best possible error. When each row of the desired sparsity pattern has at most s nonzero entries, this algorithm requires O(s/varepsilon) non-adaptive matrix-vector products with A. We also prove a matching lower-bound, showing that, for any sparsity pattern with Theta(s) nonzeros per row and column, any algorithm achieving (1+ε) approximation requires Omega(s/varepsilon) matrix-vector products in the worst case. We thus resolve the matrix-vector product query complexity of the problem up to constant factors, even for the well-studied case of diagonal approximation, for which no previous lower bounds were known.