Speaker
Description
Dense matrices arise in many areas of computational science, and hierarchical approximation methods have been developed to reduce their storage and computational costs. However, many existing approaches require access to individual matrix entries, which may not be available or prohibitively expensive to compute in important applications. A prominent example is the Hessian in Bayesian inverse problems: accurate Hessian approximations can enable fast posterior sampling, yet forming Hessian entries is costly, while Hessian–vector products can often be computed efficiently.
In this talk, we present adaptive randomized algorithms for constructing hierarchical approximations to a prescribed accuracy in a matrix-free setting. In particular, we extend the peeling paradigm to an adaptive compression strategy for HODLR matrices by approximating off-diagonal blocks at each hierarchical level to meet a global tolerance. Numerical experiments show that the proposed method achieves high accuracy more efficiently than fixed-rank schemes and than global low-rank approximations of the Hessian.