Near-optimal hierarchical matrix approximation from matrix-vector products

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^T. We prove that, for the rank-k HODLR approximation problem, our method achieves a (1+) ^ (n) -optimal approximation in expected Frobenius norm using O (k (n) /³) matrix-vector products. In particular, the algorithm obtains a (1+) -optimal approximation with O (k⁴ (n) /³) matrix-vector products, and for any constant c, an nᶜ-optimal approximation with O (k (n) ) matrix-vector products. Apart from matrix-vector products, the additional computational cost of our method is just O (n poly ( (n), k, ) ). We complement the upper bound with a lower bound, which shows that any matrix-vector query algorithm requires at least (k (n) + k/) queries to obtain a (1+) -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 introduced a novel randomly perforated matrix sketching method to further control the error in the peeling algorithm.