Fixed-sparsity matrix approximation from matrix-vector products
<|reference_start|>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 also prove a matching lower-bound, showing that, for any sparsity pattern with $\Theta(s)$ nonzeros per row and column, any algorithm achieving $(1+\epsilon)$ 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.<|reference_end|>
@article{amsel2024fixed-sparsity,
    title={Fixed-sparsity matrix approximation from matrix-vector products},
    author={Noah Amsel, Tyler Chen, Feyza Duman Keles, Diana Halikias, Cameron
  Musco, Christopher Musco},
    journal={arXiv preprint arXiv:2402.09379},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.09379},
    primaryClass={cs.DS cs.NA math.NA}
}