David Ulf Persson: Near-optimal hierarchical matrix approximation from matrix-vector products

Abstract:

We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an \(n \times n\) matrix \(A\), accessible only through matrix-vector products with \(A\) and its transpose. We prove that, for the rank-\(k\) HODLR approximation problem, the algorithm obtains a \((1 + \epsilon)\)-optimal approximation with \(O(k\log^4(n)/\epsilon^3)\) matrix-vector products. Apart from matrix-vector products, the additional computational cost of our method is just \(O(n \operatorname{poly}(\log(n), k))\). We complement the upper bound with a lower bound, which shows that any matrix-vector query algorithm requires at least \(\Omega(k \log(n) + k/\epsilon)\) queries to obtain a \((1 + \epsilon)\)-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öm 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.