HSS approximation from a number of matvecs independent of depth
For integers $k, L \ge 1$ let $N = 2^{L+1}k$, and let $\mathcal T$ be the binary tree obtained by halving $\{1, \dots, N\}$ repeatedly into sets of consecutive indices until every set has $2k$ indices. Let $\mathcal S_{L,k}$ be the set of $B \in \mathbb{R}^{N \times N}$ such that $B[I, I^c]$ and $B[I^c, I]$ have rank at most $k$ for every node $I$ of $\mathcal T$ other than the root, where $I^c = \{1, \dots, N\} \setminus I$: the HSS matrices of HSS rank at most $k$ for $\mathcal T$. Let $$E_{L,k}(A) = \min_{B \in \mathcal S_{L,k}} \|A - B\|_F^2,$$ a minimum that is attained (Amsel et al.). An algorithm sees $A$ only through matrix–vector queries, each returning $Av$ or $A^{\mathsf T}v$ for a real vector $v$ of its choice; it may choose queries adaptively, and both kinds count. Otherwise it works in exact real arithmetic, with comparisons, standard Gaussian samples and exact singular value decompositions as primitives, an SVD of an $a \times b$ matrix costing $O(ab \min(a, b))$ operations; expectations are over the algorithm's randomness, for each fixed input.
Amsel et al. obtained the guarantee below with $O(kL)$ queries, by drawing fresh Gaussian sketches at every level in a variant of a black-box algorithm of Levitt and Martinsson, which reuses the same sketches at all levels and uses $O(k)$ queries; Levitt and Martinsson support the reuse by experiments.
Problem. Are there absolute constants $C_q, C_e, c > 0$ and a single randomized algorithm that, for all integers $k, L \ge 1$ and every $A \in \mathbb{R}^{N \times N}$ with $N = 2^{L+1}k$, makes at most $C_q k$ queries in every run, uses $O(N^c)$ further arithmetic operations, and returns $B \in \mathcal S_{L,k}$ with $$\mathbb{E}\|A - B\|_F^2 \le C_e L\,E_{L,k}(A)?$$
Source: Amsel, Chen, Duman Keles, Halikias, Musco, Musco and Persson (2026), §5 (also §1.2); stated in this form by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- HSS matrices, matrix-vector queries, OpenProblemsInNLA, sketching
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{amsel2026,
author = {Amsel, Noah and Chen, Tyler and Duman Keles, Feyza and Halikias, Diana and Musco, Cameron and Musco, Christopher and Persson, David},
title = {Quasi-optimal Hierarchically Semi-separable Matrix Approximation},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {47},
number = {2},
year = {2026},
pages = {586--621},
doi = {10.1137/25M176622X},
eprint = {2505.16937},
archivePrefix = {arXiv},
}
@article{levitt2024,
author = {Levitt, James and Martinsson, Per-Gunnar},
title = {Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices},
journal = {SIAM J. Sci. Comput.},
volume = {46},
number = {3},
year = {2024},
pages = {A1747--A1763},
doi = {10.1137/22M1528574},
eprint = {2205.02990},
archivePrefix = {arXiv},
}
@article{massei2020,
author = {Massei, Stefano and Robol, Leonardo and Kressner, Daniel},
title = {hm-toolbox: {MATLAB} Software for {HODLR} and {HSS} Matrices},
journal = {SIAM J. Sci. Comput.},
volume = {42},
number = {2},
year = {2020},
pages = {C43--C68},
doi = {10.1137/19M1288048},
eprint = {1909.07909},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-re02,
author = {Townsend, Alex},
title = {{RE-02}: HSS approximation from a number of matvecs independent of depth},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RE-02/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00177, "HSS approximation from a number of matvecs independent of depth", clopen.solutions.