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).