New hierarchical matrices for fast kernel matrix-vector products with Applications to Gaussian processes and kernel ridge regression

This article presents two new multilevel hierarchical matrices to perform fast kernel matrix-vector products in d dimensions $(d>1)$, namely Hhw^, Hhw. We introduce a novel hybrid weak admissibility condition to construct these hierarchical matrices. More precisely, at coarser levels of the tree (i.e., larger blocks), we use a weak admissibility condition, wherein far-field and vertex-sharing clusters are considered admissible, while at the finer levels (i.e., smaller blocks), the adjacent clusters are treated as admissible. The admissible blocks at coarser levels of Hhw^ and Hhw are represented using semi-nested and fully nested bases, respectively. In both hierarchical matrices, the finer levels at which adjacent clusters are treated as admissible are constructed in a non-nested fashion. Thus, they can be viewed as a hybrid of H and H² matrices. We use adaptive cross approximation (ACA) and nested cross approximation (NCA) to construct non-nested and nested bases, respectively. The fast matrix-vector products are performed using the proposed hierarchical matrix formats. To evaluate the performance and usefulness of the proposed hierarchical matrices, we conduct some numerical experiments. The numerical results show that they outperform their uniform admissibility counterparts in terms of storage and matrix-vector product cost, demonstrating the effectiveness of the proposed hybrid formats. We also show that the proposed formats are competitive with the standard (or strong) admissibility-based H²-matrices. Furthermore, we showcase some interesting applications of the proposed hierarchical matrices.