Fixed-Sparsity Matrix Approximation from Matrix-Vector Products
SIAM Journal on Matrix Analysis and Applications · 30.06.2026 · 47 (2) · 483-511
DOI: 10.1137/25m1742710 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Matrix Analysis and Applications, online erschienen am 06.04.2026. Verfasst von Noah Amsel und 5 weiteren Autor:innen. Die Arbeit nennt 70 Literaturangaben. Gefördert von: Office of Naval Research, National Science Foundation.
Abstract (Originalsprache)
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]
Förderung
- Office of Naval Research
- National Science Foundation
Zitieren
APA
Amsel, N., Chen, T., Keles, F. D., Halikias, D., Musco, C., & Musco, C. (2026). Fixed-Sparsity Matrix Approximation from Matrix-Vector Products. SIAM Journal on Matrix Analysis and Applications, 47(2), 483-511. https://doi.org/10.1137/25m1742710
Vancouver
Amsel N, Chen T, Keles FD, Halikias D, Musco C, Musco C. Fixed-Sparsity Matrix Approximation from Matrix-Vector Products. SIAM Journal on Matrix Analysis and Applications. 2026;47(2):483-511. doi:10.1137/25m1742710
BibTeX
@article{Amsel2026,
author = {Amsel, Noah and Chen, Tyler and Keles, Feyza Duman and Halikias, Diana and Musco, Cameron and Musco, Christopher},
title = {Fixed-Sparsity Matrix Approximation from Matrix-Vector Products},
journal = {SIAM Journal on Matrix Analysis and Applications},
year = {2026},
volume = {47},
number = {2},
pages = {483--511},
doi = {10.1137/25m1742710}
}
EUVIMED