Quasi-optimal Hierarchically Semi-separable Matrix Approximation
SIAM Journal on Matrix Analysis and Applications · 30.06.2026 · 47 (2) · 586-621
DOI: 10.1137/25m176622x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Matrix Analysis and Applications, online erschienen am 08.05.2026. Verfasst von Noah Amsel und 6 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 76 Literaturangaben. Gefördert von: Division of Computing and Communication Foundations, Division of Graduate Education.
Abstract (Originalsprache)
We present a randomized algorithm for producing a quasi-optimal hierarchically semiseparable (HSS) approximation to an [Formula: see text] matrix [Formula: see text] using only matrix-vector products with [Formula: see text] and [Formula: see text]. We prove that, using [Formula: see text] matrix-vector products and [Formula: see text] additional runtime, the algorithm returns an HSS matrix [Formula: see text] with rank-[Formula: see text] blocks whose expected Frobenius norm error [Formula: see text] is at most [Formula: see text] times worse than the best possible approximation error by an HSS rank-[Formula: see text] matrix. In fact, the algorithm we analyze in a simple modification of an empirically effective method proposed by [J. Levitt and P.-G. Martinsson, SIAM J. Sci. Comput., 46 (2024), pp. A1747–A1763]. As a stepping stone towards our main result, we prove two results that are of independent interest: a similar guarantee for a variant of the algorithm which accesses [Formula: see text]’s entries directly, and explicit error bounds for near-optimal subspace approximation using projection-cost-preserving sketches. To the best of our knowledge, our analysis constitutes the first polynomial-time quasi-optimality result for HSS matrix approximation, both in the explicit access model and the matrix-vector product query model. 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/NoahAmsel/HSS-approximation . [Formula: see text]
Förderung
- Division of Computing and Communication Foundations
- Division of Graduate Education
Zitieren
APA
Amsel, N., Chen, T., Keles, F. D., Halikias, D., Musco, C., Musco, C., & Persson, D. (2026). Quasi-optimal Hierarchically Semi-separable Matrix Approximation. SIAM Journal on Matrix Analysis and Applications, 47(2), 586-621. https://doi.org/10.1137/25m176622x
Vancouver
Amsel N, Chen T, Keles FD, Halikias D, Musco C, Musco C, et al. Quasi-optimal Hierarchically Semi-separable Matrix Approximation. SIAM Journal on Matrix Analysis and Applications. 2026;47(2):586-621. doi:10.1137/25m176622x
BibTeX
@article{Amsel2026,
author = {Amsel, Noah and Chen, Tyler and Keles, Feyza Duman and Halikias, Diana and Musco, Cameron and Musco, Christopher and Persson, David},
title = {Quasi-optimal Hierarchically Semi-separable Matrix Approximation},
journal = {SIAM Journal on Matrix Analysis and Applications},
year = {2026},
volume = {47},
number = {2},
pages = {586--621},
doi = {10.1137/25m176622x}
}
EUVIMED