Constant-factor HSS approximation in polynomial time
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.). Algorithms work 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. showed that a greedy algorithm, which fixes the bases level by level from the leaves up by truncated SVDs, returns $B \in \mathcal S_{L,k}$ with $\|A - B\|_F^2 \le 2L\,E_{L,k}(A)$ using $O(N^2k)$ operations, and that for every $\varepsilon > 0$ some matrix makes the error of this algorithm at least $(2 - \varepsilon)E_{L,k}(A)$.
Problem. Are there absolute constants $C, c > 0$ and a single randomized algorithm that, given integers $k, L \ge 1$ and the entries of any $A \in \mathbb{R}^{N \times N}$ with $N = 2^{L+1}k$, uses $O(N^c)$ arithmetic operations and returns $B \in \mathcal S_{L,k}$, for the same $k$, with $$\mathbb{E}\|A - B\|_F^2 \le C\,E_{L,k}(A)?$$ The algorithm may be deterministic, and $C$ and $c$ do not depend on $k$, $L$ or $A$.
Source: Amsel, Chen, Duman Keles, Halikias, Musco, Musco and Persson (2026), §3.4; stated in this form by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- approximation algorithms, hierarchical matrices, HSS matrices, OpenProblemsInNLA
- 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{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-re01,
author = {Townsend, Alex},
title = {{RE-01}: Constant-factor HSS approximation in polynomial time},
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-01/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-00176, "Constant-factor HSS approximation in polynomial time", clopen.solutions.