论文标题
线性时间内核矩阵近似通过超球谐波
Linear Time Kernel Matrix Approximation via Hyperspherical Harmonics
论文作者
论文摘要
我们提出了一种新技术，用于构建用于机器学习的内核方法中出现的矩阵的低级别近似值。我们的方法对基础内核函数的新型分析扩展与数据依赖性压缩步骤配对，以进一步优化近似值。该过程以线性时间起作用，适用于任何各向同性核。此外，与接受等级为输入的普遍方法相比，我们的方法接受所需的误差耐受性作为输入。实验结果表明，我们的方法与常用的NyStrom方法相比，在给定等级的准确性和计算时间的准确性方面，在各种内核，维度和数据集中具有给定精度。值得注意的是，在许多问题设置中，我们的方法会产生近乎最佳的低级近似值。我们提供了新技术的有效开源实施，以补充我们的理论发展和实验结果。
We propose a new technique for constructing low-rank approximations of matrices that arise in kernel methods for machine learning. Our approach pairs a novel automatically constructed analytic expansion of the underlying kernel function with a data-dependent compression step to further optimize the approximation. This procedure works in linear time and is applicable to any isotropic kernel. Moreover, our method accepts the desired error tolerance as input, in contrast to prevalent methods which accept the rank as input. Experimental results show our approach compares favorably to the commonly used Nystrom method with respect to both accuracy for a given rank and computational time for a given accuracy across a variety of kernels, dimensions, and datasets. Notably, in many of these problem settings our approach produces near-optimal low-rank approximations. We provide an efficient open-source implementation of our new technique to complement our theoretical developments and experimental results.
