Approximation of high-dimensional kernel matrices by multilevel circulant matrices

作者：Song, Guohui; Xu, Yuesheng^*

来源：Journal of Complexity, 2010, 26(4): 375-405.

DOI：10.1016/j.jco.2010.02.003

• Kernel matrices
• Circulant matrices
• Multilevel circulant matrices
• Fast kernel-based methods

Kernels are important in developing a variety of numerical methods, such as approximation, interpolation, neural networks, machine learning and meshless methods for solving engineering problems. A common problem of these kernel-based methods is to calculate inverses of kernel matrices generated by a kernel function and a set of points. Due to the denseness of these matrices, finding their inverses is computationally costly. To overcome this difficulty, we introduce in this paper an approximation of the kernel matrices by appropriate multilevel circulant matrices so that the fast Fourier transform can be applied to reduce the computational cost. Convergence analysis for the proposed approximation is established based on certain decay properties of the kernels.

• 出版日期2010-8
• 单位中山大学