Structured matrix approximation from matrix-vector products
Can one recover a matrix from only matrix-vector products? If so, how many are needed? We will consider the matrix recovery problem for common matrix families, with an emphasis on hierarchical rank-structured matrices. This recovery problem arises in scientific machine learning, where one wishes to recover the solution operator of a PDE from only input-output pairs of forcing terms and solutions. Peeling algorithms are the canonical method for recovering a hierarchical matrix from matrix-vector products, however their recursive nature poses a stability issue which may deteriorate the overall quality of the approximation. Our work resolves the open question of the stability of peeling. We introduce a robust version of peeling that 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, as well as a novel randomly perforated matrix sketching method.