A kernel-independent FMM in general dimensions
A kernel-independent FMM in general dimensions
复制标题
通用维度中与内核无关的 FMM
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
William B. March;Bo Xiao;Sameer Tharakan;Chenhan D. Yu;G. Biros
介绍了一种一般维、核无关的代数快速多极方法，并将其应用于核回归。这项工作的动机是核矩阵的近似，它出现在数学物理、近似理论、非参数统计和机器学习中。现有的快速多极方法是渐近最优的，但底层常数对环境空间维度的标度很差。我们介绍了一种方法来减轻这个缺点；它只需要内核评估，并且可以很好地随问题大小、处理器数量和环境维度（只要数据集的内在维度较小）进行伸缩。我们在几个合成数据集上测试了我们的方法的性能。值得注意的是，我们最大的一次运行是在246维的1000万个点的图像数据集上进行的。
We introduce a general-dimensional, kernel-independent, algebraic fast multipole method and apply it to kernel regression. The motivation for this work is the approximation of kernel matrices, which appear in mathematical physics, approximation theory, non-parametric statistics, and machine learning. Existing fast multipole methods are asymptotically optimal, but the underlying constants scale quite badly with the ambient space dimension. We introduce a method that mitigates this shortcoming; it only requires kernel evaluations and scales well with the problem size, the number of processors, and the ambient dimension---as long as the intrinsic dimension of the dataset is small. We test the performance of our method on several synthetic datasets. As a highlight, our largest run was on an image dataset with 10 million points in 246 dimensions.