# Near-optimal hierarchical matrix approximation from matrix-vector products

arXiv: https://arxiv.org/abs/2407.04686 · HTML: https://mlsanity.com/paper/2407.04686/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2024.

## Built on by (most cited first, 2 of 2)

- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)

## Abstract (arXiv)

We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an n× n matrix A, accessible only though matrix-vector products with A and A^mathsfT. We prove that, for the rank-k HODLR approximation problem, our method achieves a (1+β)log(n)-optimal approximation in expected Frobenius norm using O(klog(n)/β3) matrix-vector products. In particular, the algorithm obtains a (1+varepsilon)-optimal approximation with O(klog4(n)/varepsilon3) matrix-vector products, and for any constant c, an nc-optimal approximation with O(k log(n)) matrix-vector products. Apart from matrix-vector products, the additional computational cost of our method is just O(n operatornamepoly(log(n), k, β)). We complement the upper bound with a lower bound, which shows that any matrix-vector query algorithm requires at least Omega(klog(n) + k/varepsilon) queries to obtain a (1+varepsilon)-optimal approximation. Our algorithm can be viewed as a robust version of widely used "peeling" methods for recovering HODLR matrices and is, to the best of our knowledge, the first matrix-vector query algorithm to enjoy theoretical worst-case guarantees for approximation by any hierarchical matrix class. To control the propagation of error between levels of hierarchical approximation, we introduce a new perturbation bound for low-rank approximation, which shows that the widely used Generalized Nystr"om method enjoys inherent stability when implemented with noisy matrix-vector products. We also introduce a novel randomly perforated matrix sketching method to further control the error in the peeling algorithm.