Fixed-Sparsity Matrix Approximation from Matrix-Vector Products

Abstract. We study the problem of approximating a matrix [Formula: see text] with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when [Formula: see text] 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 [Formula: see text] times the best possible error. When each row of the desired sparsity pattern has at most [Formula: see text] nonzero entries, this algorithm requires [Formula: see text] nonadaptive matrix-vector products with [Formula: see text]. We also prove a matching lower bound, showing that, for any sparsity pattern with [Formula: see text] nonzeros per row and column, any algorithm achieving [Formula: see text] approximation requires [Formula: see text] matrix-vector products in the worst case, even if those matrix-vector products are chosen adaptively. 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, no previous lower bounds were known. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/tchen-research/fixed_sparsity_matrix_approximation and in the supplementary materials ( Supp_Materials.zip [171KB]). [Formula: see text]