CS Paper Radar

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

Ritesh Khan, Sivaram Ambikasaran

cs.MS math.NAstat.CO ·submitted 2026-10-29 14:48 UTC · v1
unusual

Abstract

This article presents two new multilevel hierarchical matrices to perform fast kernel matrix-vector products in $d$ dimensions $(d>1)$, namely $\mathcal{H}_{hw}^{\prime}$, $\mathcal{H}_{hw}^{\prime \prime}$. 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 $\mathcal{H}_{hw}^{\prime}$ and $\mathcal{H}_{hw}^{\prime \prime}$ 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 $\mathcal{H}$ and $\mathcal{H}^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 $\mathcal{H}^2$-matrices. Furthermore, we showcase some interesting applications of the proposed hierarchical matrices.

Comment
27 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

cs.LG ·2026-09-28 ·Yueming Lyu
theory similarity 0.53
Abstract

Estimating integrals of black-box, high-dimensional functions, from expectations and kernel mean embeddings to the softmax kernel in self-attention, is a basic subroutine in machine learning. Rank-1 lattice rules suit this setting: they query the integrand only at a fixed point set and need no gradients. When the $n$ points serve as a design matrix $X\in\mathbb{R}^{n\times d}$ for a feature map, however, computing $Ψ(X)^\top v$ or $Ψ(X)w$ for an elementwise nonlinearity $Ψ$ costs $O(nd)$ time and memory for any standard quasi-Monte Carlo point set. We study subgroup rank-1 lattices, whose Korobov generator $(1,t,\dots,t^{d-1})$ uses a scalar $t$ of fixed multiplicative order $m$. Splitting $\mathbb{F}_n^\times$ into cosets of $\langle t\rangle$ reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary $Ψ$ in $O(n\log m)$ time and $O(n)$ memory, without forming $X$. Since fixing $m$ falls outside classical component-by-component theory, we prove convergence directly: via resultants with the cyclotomic polynomial $Φ_m$, the squared worst-case error in the Korobov space decays as $O(n^{-(α-1)/(m-1)})$ for prime $m\ge d+1$, and this threshold is exact. Using the splitting of $n$ in $\mathbb{Q}(ζ_m)$, averaging over the $m-1$ admissible generators improves the constant by a factor $Θ(m-1)$. Empirically, the subgroup lattice beats Gaussian and orthogonal random features and scrambled Sobol' and Halton points in 49 of 54 synthetic kernel-estimation settings and all 45 softmax-attention settings on nine real datasets, and builds a sample set with $d=2048$, $n\approx4.1\times10^7$ in 2.3 ms.

0.27

A Factor Graph Approach to Scalable Multi-Output Gaussian Process Regression

cs.LG ·2026-08-12 ·Wouter W. L. Nuijten, Esther G. van Pelt, Albert Podusenko, İsmail Şenöz, Wouter M. Kouw
similarity 0.52
Abstract · 20 pages, 8 figures, 1 Table. International Conference on Probabilistic Graphical Models 2026

Multi-output Gaussian process regression scales cubically in the number of observations times outputs, and dense kernel-matrix methods need bespoke handling whenever different outputs are observed at different inputs. We express multi-output Gaussian process regression as a Forney-style factor graph in which a nearest-neighbor chain orders a fixed candidate set of $C$ inputs into a one-dimensional sequence. Along this chain, latent Matérn processes evolve through linear-Gaussian transition factors, while the linear model of coregionalization mixes $L$ latent processes into $D$ outputs through a deterministic mixing factor and per-output scalar observation factors. Posterior computation reduces to exact Gaussian message passing on the chain at cost $\mathcal{O}(C(DL^2 + L^3))$ after chain construction, and missing observations omit their local factor without any covariance-matrix restructuring. The formulation therefore scales in the number of data samples and in the rate of missing observations, while remaining best suited to candidate sets in low input dimension. We compare the factor-graph formulation against an exact kernel-matrix baseline, a sparse-variational inducing-point baseline, and a nearest-neighbor baseline on a synthetic input-dimension sweep and on electricity time series forecasting. At low input dimension the factor-graph posterior tracks the exact kernel-matrix posterior closely, and the gap grows gradually as input dimension increases while staying competitive with both approximate baselines. On the electricity time series our factor-graph formulation matches all three baselines in forecast accuracy while scaling linearly in the number of data points, where the exact kernel-matrix method becomes infeasible and the inducing-point baseline remains substantially slower.

0.10

A GPU Engine for Sparse Matrix-Vector Products on $k^2$-Tree-Compressed Graphs

cs.DS cs.DBcs.DCcs.MS ·2026-11-02 ·Francesco Tosoni, Gabriele Mencagli
similarity 0.51
Abstract · 13 pages, 6 figures, 6 tables, 1 algorithm

The $k^2$-tree is a compact representation of Boolean matrices: it stores the recursive hierarchy of their non-empty submatrices, with neither values nor coordinates, and serves rows and columns alike. Its traversal, however, locates the children of each node by rank queries, a chain of dependent irregular loads that leaves a GPU waiting on memory. We implement sparse matrix-vector multiplication (SpMV) on $k^2$-trees for the GPU. Since the traversal does not depend on the vector, the positions of the children are static: we descend the tree one level at a time and obtain them from a parallel prefix sum or from a sampled directory of about 0.1 bits per node. Descending in tiles bounds the temporary memory by the depth of the tree, so the device memory of a product is known before it runs. The same traversal computes right and left products, for one vector or a batch, over the plus-times, Boolean and tropical semirings. We evaluate the engine on an NVIDIA GB10 and an H100 with fourteen Wikidata, Software Heritage, web and social graphs of up to 1.2 billion edges, against cuSPARSE, a grammar-compressed GPU engine and a Boolean CSR. Our results show that the tree is 2.3-27x smaller than the CSR of cuSPARSE and that, with its last internal level cached, a product takes 0.7-2.4x the time of cuSPARSE on the right and 0.27-2.6x on the left. On a 1.2-billion-edge graph, a product needs 1.1 GB on the device, 9x less than cuSPARSE. The engine is memory bounded: the $k^2$-tree is the format of choice when device memory, not time, is the constraint.

0.26

Efficient Algorithms for Subdeterminant Maximization under Partition Matroids

cs.DS cs.DM ·2026-09-16 ·Nikhil Bansal, Yuze Xu
publishedhot direction similarity 0.51
Abstract · Under submission to SODA 2027. The authors used GPT-5.5 Pro during the development of this work to explore proof strategies, search for rela…

We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes $\det(A_{S,S})$. We give an $e^{O(k)}$-approximation algorithm to find such a set $S$, where $k$ is the rank of $M$. This improves upon the current $k^{O(k)}$-approximation, and matches the current $e^k$-estimation guarantee, up to $O(1)$ factors in the exponent. Our algorithm is based on rounding the geometric max-min relaxation due to Nikolov-Singh'2016, using a continuous potential-driven process, and several new structural and analytic properties of this relaxation.

0.31

A Bochner Weitzenböck Decomposition for Cellular Sheaf Laplacians, Curvature and Neural Sheaf Diffusion

cs.CG cs.LG ·2026-10-20 ·Francesco Maria Guadagnuolo, Alessio Borgi, Dorina Thanou, Pietro Liò
theory similarity 0.51
Abstract

We extend the Bochner-Weitzenböck decomposition to cellular sheaf Laplacians, splitting it into a positive semidefinite term, the Bochner sheaf Laplacian, and a block diagonal term, the Forman curvature. We show that the Bochner Laplacians form a class of cellular sheaves that extends both connection and matrix-weighted Laplacians, and generalizes signed graphs to $d$ dimensions. We give a holonomy characterization of their kernel, prove the related Cheeger inequalities, and attach to them a random walk that generalizes the Gremban expansion. For the Forman term, we prove a discrete Bochner theorem, which bounds the first cohomology of a cellular sheaf with nonnegative curvature, and we read the whole decomposition as an opinion-dynamics model. We then apply this machinery to Sheaf Neural Networks, whose learnt Laplacian is otherwise unobserved. The Bochner interpretation yields a node-level conviction score that acts as an operational importance measure under frozen-model interventions, while the Forman profile provides a local descriptor of the learnt operator.

0.48

What Must Survive? Exact Task-Information--State Frontiers Under Partial Task Revelation

cs.LG cs.IT ·2026-09-18 ·Ronald Katende
similarity 0.51
Abstract · 12 pages, 2 figures, 1 table. Substantially expanded version: added sharp approximate bounds, overlap-deficit theory, approximation guarante…

A state may need to be compressed before its exact downstream task is known. For a finite family of linear task operators $\{T_u\}_{u\in\U}$, we characterize exactly how much state must survive when only one of $K$ coarse task messages is available at compression time: $$p^*(K)= \min_{\substack{\Pcal\text{ partition of }\U\\|\Pcal|\le K}} \max_{C\in\Pcal}\rank(T_C),$$ where $T_C$ stacks the tasks that remain unresolved within cell $C$. Thus task information reduces retained state precisely by separating tasks whose joint task-visible subspace is expensive. We derive the dual bit frontier, an irreducible common-core floor, and a sharp singular-value characterization for nonzero tolerance. For overlapping task families, a cumulative overlap deficit places the exact frontier within an additive $Δ$ of weighted load balancing. Optimal partitioning is strongly NP-hard, yet direct-sum families admit classical approximation guarantees and a PTAS. We stress-test the theory on learned task operators from CIFAR-10, Fashion-MNIST, SVHN, and Burgers observables. For Burgers with $K=2$ and $\eps=0.35$, a constructive partition attains $p=4$, while balanced random partitions require median $p=6$, with held-out worst standardized RMSE $0.0368$. The results distinguish uniform task sufficiency from distributional and decision-level performance.

0.37

Singularities of Non-negative Matrix Factorization and their application to Bayesian inference

cs.LG stat.MLmath.ST ·2026-09-28 ·Naoki Hayashi, Yota Maeda, Yasushi Esaki
theory similarity 0.50
Abstract · 23 pages

Non-negative matrix factorization (NMF) is a singular statistical model whose Bayesian asymptotics are governed by the real log canonical threshold (RLCT). We study the local geometry of the factorization map and derive an upper bound for the RLCT of NMF. Let $H$ be the model inner dimension and $H_0$ the non-negative rank of the true $M\times N$ matrix. Assuming that the true matrix admits a strictly positive factorization of inner dimension $H_0$ in the interior of the parameter domain, we prove, for smooth positive priors, that $λ\leq \{(H-H_0)\min(M,N)+H_0(M+N-H_0)\}/2$. This bound strictly improves the previous bound when $H_0\geq3$. The proof uses a local analytic normal form that separates independent linear coordinates from a residual matrix product. When $H=H_0$ also equals the ordinary rank of the true matrix, we obtain the exact value $λ=H_0(M+N-H_0)/2$. Under the standard assumptions of singular learning theory, these results bound the leading coefficients of the expected Bayesian generalization error and the Bayesian free energy.

0.22

Information Limits of Low-Rank Approximation Certification

cs.AI math.OCcs.IT ·2026-10-02 ·Kang Liu, Bohao Qu
theorycode/data similarity 0.50
Abstract

Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across \(W\) paths, a concentration bound exploiting shared residual energy yields a \(\sqrt{\log(W+1)}\) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders \(N^{1/3}\) and \(N^{2/3}\) for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/

0.29