Optimal matvec query complexity of HODLR approximation
Let $k \ge 1$ and $L \ge 2$ be integers, $n = 2^L k$ and $0 < \varepsilon < 1/2$. Let $\mathcal H_{n,k}$ be the set of real $n \times n$ HODLR matrices with rank parameter $k$: a matrix of order at most $k$ is unrestricted, and a larger one belongs to the class when its two off-diagonal blocks of half the order have rank at most $k$ and its two diagonal blocks belong to the class. An algorithm sees the input $A \in \mathbb{R}^{n \times n}$ only through queries, each returning $Av$ or $A^{\mathsf T}v$ for a real vector $v$ of its choice; it may choose queries adaptively and use randomness, both kinds of query count, and computation between queries is free and may be any measurable computation. Let $q_*(n, k, \varepsilon)$ be the least $q$ for which some such algorithm, making at most $q$ queries on every input and in every run, returns $B \in \mathcal H_{n,k}$ with $$\Pr\Bigl[\|A - B\|_F \le (1 + \varepsilon) \min_{H \in \mathcal H_{n,k}} \|A - H\|_F\Bigr] \ge 0.99$$ for every $A$, the probability being over the algorithm's randomness.
Chen, Duman Keles, Halikias, Musco, Musco and Persson gave a non-adaptive algorithm showing $q_*(n, k, \varepsilon) = O(kL^4/\varepsilon^3)$, and noted that $n$ queries, which determine $A$, suffice. They proved $q_*(n, k, \varepsilon) = \Omega(kL)$, and $q_*(n, k, \varepsilon) = \Omega(kL + k/\varepsilon)$ when $n \ge c_0 k/\varepsilon$ for an absolute constant $c_0$.
Problem. Determine $q_*(n, k, \varepsilon)$ up to absolute constant factors, as a function of $k$, $L$ and $\varepsilon$ jointly.
Source: Stated by OpenProblemsInNLA, after Chen, Duman Keles, Halikias, Musco, Musco and Persson (2025), who ask at the end of §6 for a lower bound that combines k, log(n/k) and 1/ε multiplicatively.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- HODLR matrices, matrix-vector queries, OpenProblemsInNLA, query complexity
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@inproceedings{chen2025,
author = {Chen, Tyler and Duman Keles, Feyza and Halikias, Diana and Musco, Cameron and Musco, Christopher and Persson, David},
title = {Near-optimal hierarchical matrix approximation from matrix-vector products},
booktitle = {Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2025},
pages = {2656--2692},
doi = {10.1137/1.9781611978322.87},
eprint = {2407.04686},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-re03,
author = {Townsend, Alex},
title = {{RE-03}: Optimal matvec query complexity of HODLR approximation},
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-03/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Resolution claims
For the fixed-partition HODLR approximation problem with $n=2^Lk$, this note develops the bounds $c\min\{n,kL/\varepsilon+k/\varepsilon^2\}\le q_*(n,k,\varepsilon)\le C\min\{n,kL^2/\varepsilon+kL/\varepsilon^2\}$. The upper bound is obtained by a row-isotropic perturbation inequality for truncated SVD, a noisy Gaussian Nyström calculation, a constant-accuracy perforated pilot, and a globally shared final regression. The new lower term $kL/\varepsilon$ uses weighted hierarchical Stiefel frames, large fixed rank-constrained anchors, and a …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-09 | Open → Partially resolved | The registry's curators | Sharper bounds for fixed-partition HODLR approximation v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscript/re03_extended_results.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00178, "Optimal matvec query complexity of HODLR approximation", clopen.solutions.