Improved fast Gauss transform with variable source scales
Improved fast Gauss transform with variable source scales
复制标题
改进的具有可变源尺度的快速高斯变换
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
R. Duraiswami
中科院分区：
文献类型：
--
作者：
V. Raykar;R. Duraiswami
计算多变量高斯核函数的和是计算统计和机器学习中的一个关键计算任务。这种和的直接评估的计算成本的规模作为核函数和评估点的数量的乘积。Greengard和Strain（1991）提出的快速高斯变换可以加速低维求和。Yang et al.（2003）提出了一种适用于高维问题的快速高斯变换的扩展（改进的快速高斯变换或IFGT），并将其应用于Yang et al.（2004）的一些机器学习问题。然而，该算法仅限于恒定带宽高斯的情况。在许多应用中，如果使用可变带宽函数，则性能得到改善。我们提出了一个扩展的IFGT算法，允许可变带宽高斯内核。算法的细节，误差界和数值实验。例如，对于N = M = 1，024，000，直接评估需要约2.6天，而快速评估仅需要4.65分钟，误差约为10 - 5。
Evaluating sums of multivariate Gaussian kernels is a key computational task in many problems in computational 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 original fast Gauss transform due to Greengard and Strain (1991) can accelerate such sums in low dimensions. Yang et al. (2003) presented an extension of the fast Gauss transform (the improved fast Gauss transform or IFGT) that was suitable for higher dimensional problems, and applied it to some machine learning problems in Yang et al. (2004). However, this algorithm was restricted to the case of constant bandwidth Gaussians. In many applications performance is improved if variable bandwidth functions are used. We present an extension to the IFGT algorithm that allows variable bandwidth Gaussian kernels. Algorithm details, error bounds and numerical experiments are presented. For example for N = M = 1, 024, 000 while the direct evaluation takes around 2.6 days the fast evaluation requires only 4.65 minutes with an error of around 10−5.