Fast Evaluation of Radial Basis Functions: Moment-Based Methods

Abstract

This paper presents a new method for the fast evaluation of univariate radial basis functions of the form $s(x) = \sum_{n=1}^N d_n \phi ( | x -x_n | ) $ to within accuracy $\epsilon$. The method can be viewed as a generalization of the fast multipole method in which calculations with far field expansions are replaced by calculations involving moments of the data. The method has the advantage of being adaptive to changes in $\phi$. That is, with this method changing to a new $\phi$ requires only coding a one- or two-line function for the (slow) evaluation of $\phi$. In contrast, adapting the usual fast multipole method to a new $\phi$ involves much mathematical analysis of appropriate series expansions and corresponding translation operators, followed by a substantial amount of work expressing this mathematics in code.