Approximation of high-dimensional kernel matrices by multilevel circulant matrices (Q990819)

The authors approximate the kernel matrix of a high-dimensional kernel by a nice matrix with a significantly lower computational cost when calculating the inverse of its regularized matrix. Multilevel circulant matrices are a good choice since they are convenient to calculate their inverses. The built-in periodicity of these matrices allows the use of the multi-dimensional fast Fourier transform in calculating their inverses at the cost of \(O(n\log n)\) multiplications. The fast discrete algorithms for sparse Fourier expansions of high-dimensional data can be applied to obtain an even faster algorithm. Convergence for the approximation of kernel matrices by multilevel circulant matrices is analyzed under the assumption that the kernel matrices have an exponential or polynomial decay when their elements are both away from the diagonal and from the corners of the matrices at each level. Compactly supported kernels are also considered. The development presented in this paper for high-dimensional kernels is not a trivial extension of the one-dimensional results.