Approximation of kernel matrices in machine learning

Date of Award


Degree Type


Degree Name

Doctor of Philosophy (PhD)




Yuesheng Xu


Kernel, Machine learning, Hilbert space

Subject Categories

Physical Sciences and Mathematics


Kernels are popular in a variety of fields such as approximation, interpolation, meshless methods, neural networks and machine learning. A common problem of these kernel-based methods is to calculate the inverses of the matrices generated by a kernel function and a set of points. This work focuses on developing fast algorithms for calculating the inverses by approximating the kernel matrices with related multilevel circulant matrices so that the fast Fourier transform can apply to reduce the computational cost. In the first part of this thesis, we introduce two classes of matrices that contain the kernel matrices under different assumptions of the kernel function and the data points. Some properties of these two classes of matrices such as the approximation behavior of the elements and some functions of the inverses are presented. Moreover, we give the convergence analysis of approximating the kernel matrices with related multilevel circulant matrices based on properties of these two classes of matrices. The second part of this thesis talks about the applications of this approximation technique in machine learning. After introducing the formulation of two common problems in machine learning, we present some fast algorithms for these two problems and give the convergence analysis based on the results obtained in Part I.


ISBN 9781109507003