Smoothed Analysis of Rank Growth in Kernel Matrices with Randomized Particle Distributions
Please login to view abstract download link
Kernel matrices play a central role in numerical methods for differential equations, fast algorithms, and kernel-based techniques in data science and machine learning. While hierarchical low-rank methods are widely used to accelerate computations involving such matrices, their effectiveness depends strongly on the rank structure of kernel interaction blocks. Most existing theoretical analyses assume structured or quasi-uniform particle distributions, an assumption that is rarely satisfied in practical applications. This talk focuses on the rank behavior of matrices arising from singular kernel functions when source and target particles are distributed arbitrarily within neighboring domains that share a boundary. A smoothed analysis framework is employed in which arbitrary particle configurations are modeled as realizations of an underlying random distribution. Within this framework, theoretical results on the expected rank and variance of kernel matrices corresponding to different neighbor interactions are discussed, highlighting the influence of geometric configuration on rank growth. Numerical experiments in one, two, and three spatial dimensions are presented to illustrate the predicted rank behavior and variability across interaction types. The results demonstrate that, despite the presence of unstructured particle layouts, rank growth remains controlled in a probabilistic sense. Overall, the presentation provides theoretical insight into the robustness and computational complexity of hierarchical matrix algorithms, particularly those based on weak admissibility, and helps explain their effectiveness for realistic particle distributions encountered in large-scale scientific computing.
