2025-11-15T09:01:12.242557

Numerical Methods for Kernel Slicing

Rux, Hertrich, Neumayer

Kernels are key in machine learning for modeling interactions. Unfortunately, brute-force computation of the related kernel sums scales quadratically with the number of samples. Recent Fourier-slicing methods lead to an improved linear complexity, provided that the kernel can be sliced and its Fourier coefficients are known. To obtain these coefficients, we view the slicing relation as an inverse problem and present two algorithms for their recovery. Extensive numerical experiments demonstrate the speed and accuracy of our methods.

academic

Numerical Methods for Kernel Slicing

基本信息

论文ID: 2510.11478
标题: Numerical Methods for Kernel Slicing
作者: Nicolaj Rux (Chemnitz University of Technology), Johannes Hertrich (Université Paris Dauphine-PSL and Inria Mokaplan), Sebastian Neumayer (Chemnitz University of Technology)
分类: math.NA, cs.NA
发表时间: October 14, 2025
论文链接: https://arxiv.org/abs/2510.11478v1

摘要

核函数在机器学习中对建模交互关系至关重要。然而，相关核函数求和的暴力计算复杂度随样本数量呈二次增长。最近的傅里叶切片方法可以将复杂度降低到线性，前提是核函数可以被切片且其傅里叶系数已知。为获得这些系数，本文将切片关系视为逆问题，提出了两种恢复算法。大量数值实验证明了方法的速度和准确性。

研究背景与动机

核心问题

核方法在机器学习中广泛应用于密度估计、支持向量机分类、主成分分析、最大均值差异(MMD)等任务。这些应用的计算瓶颈通常是评估如下形式的表达式：

$s_m := \sum_{n=1}^N F(\|x_n - y_m\|)w_n, \quad m = 1,\ldots,M$

其中 $F \in C([0,\infty))$ 是径向基函数， $x_1,\ldots,x_N, y_1,\ldots,y_M \in \mathbb{R}^d$ 是样本点， $w \in \mathbb{R}^N$ 是权重。

计算复杂性挑战

直接计算需要 $O(NMd)$ 次操作，对于大数据集不可行。经典方法如快速傅里叶求和和快速多极方法虽然能将复杂度降低到 $O(M+N)$ ，但由于依赖快速傅里叶变换或空间分割，在维度 $d > 4$ 时会出现指数依赖，使其不可行。

切片算法的优势

切片算法的基本思想是寻找函数 $f \in L^1_{loc}([0,\infty))$ 使得：

$F(\|x\|) = \frac{1}{\omega_{d-1}} \int_{S^{d-1}} f(|\langle\xi, x\rangle|)d\xi$

其中 $\omega_{d-1} = 2\pi^{d/2}/\Gamma(d/2)$ 是 $d$ 维球面的表面测度。通过离散化积分，核求和可以简化为一维情况，使用快速傅里叶求和高效计算。

核心贡献

将切片函数恢复问题形式化为逆问题，建立了完整的理论框架
提出两种数值算法用于恢复快速傅里叶求和所需的余弦级数系数
提供严格的误差估计，包括前向误差和切片误差的分析
广泛的数值实验验证了方法在各种核函数上的效率和准确性
扩展了方法的适用范围，无需解析知识即可处理未知切片函数的核

方法详解

任务定义

给定径向基函数 $F: [0,\infty) \to \mathbb{R}$ ，寻找函数 $f: [0,\infty) \to \mathbb{R}$ 使得切片关系 $F = S_d[f]$ 成立，其中 $S_d$ 是广义Riemann-Liouville分数积分算子：

$S_d[f](s) = \int_0^1 f(ts)\varrho_d(t)dt$

其中 $\varrho_d(t) := c_d(1-t^2)^{(d-3)/2}$ ， $c_d := \frac{2\Gamma(d/2)}{\sqrt{\pi}\Gamma((d-1)/2)}$ 。

模型架构

1. 优化问题构建

将切片函数恢复转化为正则化最小化问题：

$\hat{a} = \arg\min_{a \in \mathbb{R}^K} \|S_d[f_a] - F\|_H^2 + \tau^2\|f_a\|_G^2$

其中 $f_a = C^{-1}[a]$ 是 $K$ 项余弦级数：

$f_a(t) = a_0 + \sqrt{2}\sum_{k=1}^{K-1} a_k \cos(\pi kt)$

2. 空间域方法（算法1）

矩阵构建：计算 $h_k := S_d[g_k]$ ，其中 $g_k$ 是余弦基函数
离散化：使用Gauss-Legendre求积法近似积分
求解：解决最小二乘问题 $\|\hat{H}^T a - \hat{b}\|_2^2 + \tau^2\|Da\|_2^2$

3. 频域方法（算法2）

算子表示：构建算子 $S := C \circ S_d \circ C^{-1}$ 的矩阵表示
系数计算：利用关系 $S_{j,k} = S_d[\text{sinc}(\cdot + j) + \text{sinc}(\cdot - j)](k)$
优化求解：在频域空间中求解正则化问题

技术创新点

理论基础：建立了切片算子 $S_d$ 在不同函数空间上的有界性理论
数值稳定性：通过Tikhonov正则化处理病态问题
误差分解：将总误差分解为前向误差和切片误差两部分
收敛性分析：证明了在函数光滑性假设下的收敛率

实验设置

数据集

使用多种径向基函数进行测试：

Gauss: $F(s) = \exp(-s^2/(2c^2))$
Laplace: $F(s) = \exp(-c|s|)$
逆多二次函数(IMQ): $F(s) = (c^2 + s^2)^{-1/2}$
薄板样条(TPS): $F(s) = (cs)^2\log(|cs|)$
对数核(LOG): $F(s) = \log(|cs|)$
Bump函数和多二次函数(MQ)

评价指标

前向误差： $|F_K(s) - F(s)|$
相对L2误差： $\|s - \hat{s}\|_2/\|s\|_2$
运行时间比较

对比方法

直接方法：当解析解 $f = S_d^{-1}[F]$ 已知时的截断傅里叶级数
PyKeOps：高度优化的GPU暴力计算包
三种配置：S-L2-H1, F-L2-H1, F-H1-H1

实现细节

使用 $L = 2^{10}$ 个求积点
域中 $K = 2^8$ 个余弦系数，值域中 $J = 2^{10}$ 个
正则化参数 $\tau \in \{10^{-6}, 10^{-7}, 10^{-4}\}$

函数	S-L2-H1	F-L2-H1	F-H1-H1	Direct
Gauss	6.53×10⁻³	6.62×10⁻³	6.61×10⁻³	6.56×10⁻³
Laplace	8.58×10⁻³	8.32×10⁻³	1.30×10⁻²	5.90×10⁻³
IMQ	2.25×10⁻³	2.27×10⁻³	2.28×10⁻³	2.26×10⁻³
LOG	1.00×10⁻¹	1.80×10⁻¹	1.55×10⁻¹	2.98×10¹