Fixed-sparsity matrix approximation from matrix-vector products

We study the problem of approximating a matrix $\mathbf{A}$ with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when $\mathbf{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 $\mathbf{A}$. We proceed to prove a matching lower-bound. Specifically, we show that for any $s\geq 1$, there are matrices $\mathbf{A}$ such that, for any sparsity pattern with $\Theta(s)$ nonzeros per row and column, any algorithm which obtains a $(1+\varepsilon)$ accurate approximation of the given sparsity from matrix-vector products requires at least $\Omega(s/\varepsilon)$ matrix-vector products. Our bounds therefore 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.