EUVIMEDEUVIMED entdecken
Crossref

Quasi-optimal Hierarchically Semi-separable Matrix Approximation

Noah Amsel, Tyler Chen, Feyza Duman Keles, Diana Halikias, Cameron Musco, Christopher Musco, David Persson

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →