A hybrid stochastic interpolation and compression method for kernel matrices.

Area of Science:

• Scientific Computing
• Machine Learning
• Numerical Analysis

Background:

• Kernel functions are crucial in scientific computing and machine learning.
• Dense kernel matrices present significant computational challenges at large scales.
• Existing methods struggle with efficiency for complex data structures.

Purpose of the Study:

• To develop fast algorithms for compressing kernel matrices.
• To reduce the computational cost of matrix operations in kernel-based applications.
• To enable efficient handling of complex data structures like high-dimensionality and manifolds.

Main Methods:

• Utilized polyharmonic spline interpolation with radial basis functions and polynomial bases.
• Employed flexible random sampling of data points for kernel functions.
• Integrated QR sampling strategy with fast stochastic Singular Value Decomposition (SVD).

Main Results:

• Achieved computational complexity of O(N) for low-rank matrices and O(N log N) for general matrices with hierarchical structures, where N is the number of degrees of freedom.
• Demonstrated significant reductions in computation cost for kernel matrix operations.
• Validated accuracy and efficiency across various data domains and kernel functions.

Conclusions:

• The proposed fast kernel matrix compression algorithms offer a computationally efficient solution for large-scale problems.
• The method's flexibility makes it suitable for diverse and complex data structures.
• This approach enhances the feasibility of kernel-based methods in resource-intensive applications.