New hierarchical matrices for fast kernel matrix-vector products with Applications to Gaussian processes and kernel ridge regression
Abstract
This article presents two new multilevel hierarchical matrices to perform fast kernel matrix-vector products in d dimensions (d>1), namely ℋhw′, ℋhw′ ′. 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 \textbf{far-field} and \textbf{vertex-sharing} clusters are considered admissible, while at the finer levels (i.e., smaller blocks), the \textbf{adjacent} clusters are treated as admissible. The admissible blocks at coarser levels of ℋhw′ and ℋhw′ ′ 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 ℋ and ℋ2 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 ℋ2-matrices. Furthermore, we showcase some interesting applications of the proposed hierarchical matrices.
Related
- Asymptotic expansion of smooth functions in deterministic and iid Haar unitary matrices, and application to tensor products of matrices
- UPPER TAIL PROBABILITY ESTIMATES OF SUPREMA OF GAUSSIAN PROCESSES BY MATRICES, A NUMBER THEORETIC EXAMPLE
- Quantitative universality for products of i.i.d. random matrices
- Asymptotic spectral properties and extreme eigenvalues of sample correlation matrices from nonstationary high-dimensional VAR processes
- On the Hadamard form of hierarchical spline Galerkin matrices and their efficient assembly in isogeometric analysis
BibTeX
@misc{khan2026hierarchical,
title = {{New hierarchical matrices for fast kernel matrix-vector products with Applications to Gaussian processes and kernel ridge regression}},
author = {Ritesh Khan and Sivaram Ambikasaran},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40195},
eprint = {2610.40195},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40195},
}
RIS
TY - UNPB
TI - New hierarchical matrices for fast kernel matrix-vector products with Applications to Gaussian processes and kernel ridge regression
AU - Ritesh Khan
AU - Sivaram Ambikasaran
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40195
UR - https://arxiv.org/abs/2610.40195
AB - This article presents two new multilevel hierarchical matrices to perform fast kernel matrix-vector products in d dimensions (d>1), namely ℋ_hw^′, ℋ_hw^′ ′. 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 \textbf{far-field} and \textbf{vertex-sharing} clusters are considered admissible, while at the finer levels (i.e., smaller blocks), the \textbf{adjacent} clusters are treated as admissible. The admissible blocks at coarser levels of ℋ_hw^′ and ℋ_hw^′ ′ 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 ℋ and ℋ^2 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 ℋ^2-matrices. Furthermore, we showcase some interesting applications of the proposed hierarchical matrices.
ER -