Metraipolis › archive › dc_b8324cc413e1
Quasi-Optimal Randomized Recovery of $\mathcal{H}^2$ Matrices — arXiv:2610.04574
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.04574
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T14:01:02.861Z
- SHA-256 of the archived text
339943502e4f6026c3e122419f2635fc6e7ebd207802f6512f29816d996615b9- Stable URL of this page
https://metraipolis.com/documento/dc_b8324cc413e1
How to cite
Quasi-Optimal Randomized Recovery of $\mathcal{H}^2$ Matrices — arXiv:2610.04574 — arXiv (en), https://arxiv.org/abs/2610.04574 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b8324cc413e1 (Metraipolis archive dc_b8324cc413e1, sha256 339943502e4f6026c3e122419f2635fc6e7ebd207802f6512f29816d996615b9)
BibTeX
@misc{dcb8324cc413e1,
title = {Quasi-Optimal Randomized Recovery of $mathcalH^2$ Matrices — arXiv:2610.04574},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.04574},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b8324cc413e1; sha256 339943502e4f6026c3e122419f2635fc6e7ebd207802f6512f29816d996615b9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.04574. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
An $\mathcal H^2$ matrix represents well-separated interactions using nested low-rank bases while retaining nearby interactions explicitly. We consider the problem of constructing an explicit, strongly admissible $\mathcal H^2$ approximation using only products with the matrix and its adjoint, and develop two randomized recovery algorithms on an adaptive geometric hierarchy. Carried recovery begins with a single pair of dense Gaussian test matrices, without hierarchy-specific probing, and updates the resulting forward--adjoint sketches across levels. All operator samples can therefore be acquired in one batch. Resketched recovery applies the same recovery procedure using fresh Gaussian test matrices at each level. For this variant, we prove a global quasi-optimal bound on the expected Frobenius error relative to the best approximation with the prescribed hierarchy, rank bounds, and retained near-neighbor pattern. Carried recovery requires only $O(k+p)$ applications of the matrix and its adjoint, independent of tree depth, whereas resketched recovery requires $O((k+p)\log(N/k))$ on trees of logarithmic depth. Here $N$ is the matrix dimension, $k$ the maximum prescribed box rank, and $p$ the oversampling parameter. These bounds assume bounded near-neighbor counts and $O(k)$ local dimensions. Experiments on Laplace, Dirichlet-to-Neumann, and Helmholtz operators in two and three dimensions with up to $1.28$ million unknowns show that, with sufficient oversampling, carried recovery achieves nearly refinement-independent error and accuracy comparable to resketched recovery while using many fewer operator applications. Its compressed application cost scales linearly for a fixed rank. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.NA, nuovi lavori del giorno). Categorie arXiv: Numerical Analysis (math.NA). Pagina del lavoro: https://arxiv.org/abs/2610.04574 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T12:21:32.328Z dalla pagina https://arxiv.org/list/math.NA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).