Evaluating sums of multivariate Gaussian kernels is a key computational task in many problems in computer vision, statistics and machine learning. The computational cost of the direct evaluation of such sums scales as the product of the number of kernel functions and the evaluation points. The fast Gauss transform (FGT) reduces the computational complexity of the evaluation of the sum of N Gaussians at M points in d dimensions from O(MN) to O(M+N). The FGT was first proposed by Greengard and Strain and applied successfully to a few lower dimensional applications in mathematics and physics. However the performance degrades exponentially with increasing dimensionality, which makes it impractical for dimensions greater than three. We presented an extension of the fast Gauss transform (the improved fast Gauss transform or IFGT) that was suitable for higher dimensional problems. Use of new data structures and an efficient factorization reduced the constant factor was to asymptotically polynomial order in the dimension.
There are many applications of this new algorithm. We have applied it to problems in computer vision (tracking and segmentation via the mean-shift algorithm) and learning (regularized support vector classifiers and Gaussian process regression). In each case use of the IFGT results in a dramatic improvement in the performance of the algorithm, reducing the asymptotic complexity from O(N 3) or O(N 2) to linear order.