Quasi-Optimal Randomized Recovery of ℋ2 Matrices
Abstract
An ℋ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 ℋ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.
Related
- Eigenvector distributions and optimal shrinkage estimators for large covariance and precision matrices
- An optimal pinching theorem on compact minimal submanifolds in the Euclidean spheres via eigenvalues of fundamental matrices
- Multi-Index Recovery for Total-Degree Multivariate Vandermonde Matrices
- An optimal pinching theorem on compact minimal submanifolds in the Euclidean spheres via eigenvalues of fundamental matrices II
- Seriation of Tœplitz and latent position matrices: Optimal rates and computational trade-offs
BibTeX
@misc{yesypenko2026quasioptimal,
title = {{Quasi-Optimal Randomized Recovery of $\mathcalH^2$ Matrices}},
author = {Anna Yesypenko},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04574},
eprint = {2610.04574},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04574},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quasi-Optimal Randomized Recovery of ℋ^2 Matrices
AU - Anna Yesypenko
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04574
UR - https://arxiv.org/abs/2610.04574
AB - An ℋ^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 ℋ^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.
ER -