A hybrid stochastic interpolation and compression method for kernel matrices.
A hybrid stochastic interpolation and compression method for kernel matrices.
复制标题
核矩阵的混合随机插值和压缩方法。
DOI：
10.1016/j.jcp.2023.112491
复制
发表时间：
2023
影响因子：
4.1
通讯作者：
Chen,Duan
中科院分区：
文献类型：
--
作者：
Chen,Duan
核函数在许多科学计算和机器学习问题中起着举足轻重的作用，但核函数往往会产生稠密的核矩阵，这给大规模计算带来了巨大的挑战。为了解决这个问题，我们开发了一套快速的核矩阵压缩算法，它可以减少相关应用中的矩阵运算的计算成本。这些算法的基础是多调和样条插值，它包括一组径向基函数，允许灵活选择插值节点，和一组多项式基函数，保证插值的可解性和收敛性。利用这些性质，交互核函数中的原始数据点可以灵活地随机采样，因此该方法适用于高维、随机分布或流形等复杂数据结构。为了进一步提高算法的精度和效率，我们的方案采用了QR采样策略，并结合最近开发的快速随机SVD，形成一个混合方法。如果自由度的总数是N，则压缩算法对于低秩矩阵的复杂度为O（N），对于具有层次结构的一般矩阵的复杂度为O（N log N）。对不同区域和不同核函数的数据进行了数值计算，验证了该方法的准确性和有效性。
Kernel functions play a pivotal role in a wide range of scientific computing and machine learning problems, but they ofter result in dense kernel matrices that impose great challenges in computational costs at large scale. To address this issue, we develop a set of fast kernel matrix compressing algorithms, which can reduce computation cost of matrix operations in the related applications. The foundation of these algorithms is the polyharmonic spline interpolation, which encompass a set of radial basis functions that allow flexible choices of interpolating nodes, and a set of polynomial basis functions that guarantee the solvability and convergence of the interpolation. With these properties, original data points in the interacting kernel function can be randomly sampled with great flexibility, so the proposed method is suitable for complicated data structures, such as high-dimensionality, random distribution, or manifold. To further boost the algorithm accuracy and efficiency, our scheme incorporates a QR sampling strategy, and combined with a recently developed fast stochastic SVD to form a hybrid method. If the overall number of degree of freedom is N, then the compressing algorithm has complexity of O (N) for low-rank matrices, and O (N log N) for general matrices with a hierarchical structure. Numerical results for data on various domains and different kernel functions validate the accuracy and efficiency of the proposed method.