Low-rank approximation of analytic kernels

技术摘要：解析核的低秩逼近

问题陈述
科学计算和数据科学中的许多矩阵与核都表现出“近低秩”结构，这意味着它们可以用低秩矩阵在各种范数下进行良好逼近。理解这种结构的理论基础对于分析和开发高性能算法至关重要。虽然现有的解释依赖于光滑函数通过多项式进行逼近（产生基于 Bernstein 椭圆的指数级衰减）或位移结构（通过 Sylvester 方程），但这些方法往往会产生过于悲观的误差界，或者无法充分利用核的解析性质。具体而言，基于多项式插值的现有界限其衰减速率由最大的 Bernstein 椭圆决定，这可能显著小于有理逼近所能实现的真实收敛速率。

方法论
本文引入了一个新的框架，用于界定由在紧集 $E$ 上对一个变量（设为 $y$）具有解析延拓性的核 $K(x,y)$ 所生成的矩阵的低秩逼近误差。该核在包含不相交紧集 $F$ 的一个大开集内是解析的。

核心方法论是源自 Cauchy 积分公式的算子分解：
$$K = K' \mathcal{C}$$
其中：

1. $\mathcal{C}$ 是一个 Cauchy 变换算子，将 $L^2_\mu(E)$ 映射到解析函数空间 $H(F)$。
2. $K'$ 是一个“Grothendieck 对偶”算子，将 $H(F)$ 映射到 $C(D)$。该算子将 $K(x, \cdot)$ 在 $F$ 中的奇异性转化为对定义在 $F$ 上的函数的作用（例如求值、微分或卷积）。

低秩逼近 $K_n$ 通过用秩为 $n$ 的算子 $\mathcal{C}_n$ 来逼近 Cauchy 变换 $\mathcal{C}$ 而构建。$\mathcal{C}_n$ 的核是由有理函数 $\phi \in R_n$（类型为 $(n,n)$ 的有理函数）导出的。误差界由 Cauchy–Zolotarev 数控制，定义为：
$$Z_n(L^p_\mu(E), L^q_\nu(F)) = \inf_{\phi \in R_n} \left\| \frac{\phi(z)^{-1}\phi(y)}{y-z} \right\|_{L^p_\mu(E) \to L^q_\nu(F)}$$
这些数随 $n$ 指数级衰减，其速率由共形模 $\rho(E,F)$ 决定，该模量量化了 $E$ 与 $F$ 之间的分离程度。

证明 $K_n$ 的构造等价于对核 $K(x, \cdot)$ 进行有理插值。插值节点和极点即为最小化 Cauchy–Zolotarev 数的优化有理函数 $\phi$ 的根与极点。对于特定几何结构（例如不相交区间），这些最优函数即为经典的 Zolotarev 有理函数。

主要贡献

1. 理论框架： 本文建立了定理 1.1，提供了一个涉及 Cauchy–Zolotarev 数和 Grothendieck 对偶算子 $K'$ 范数的低秩逼近误差界。这将在统一的框架下处理连续核与离散矩阵/张量。
2. 卓越的收敛速率： 理论表明，收敛速率受控于共形模 $\rho(E,F)$，这通常比用于多项式插值界限的最大 Bernstein 椭圆参数要大。这解释了为什么有理逼近在处理解析核时往往优于多项式逼近。
3. 构造性算法： 证明是构造性的，表明最优低秩逼近器是一个有理插值器。插值节点和极点被明确识别为最优 Zolotarev 有理函数的根与极点。
4. 通过对偶性体现的位移结构： 本文通过 Grothendieck 对偶性的视角揭示了解析核中潜在的位移结构，将核的解析延拓性质与位移方程的可解性联系起来。
5. 处理奇异性： 该框架能够处理 Cauchy 变换无界的情况（例如 $L^2 \to L^1$），只要 $n \ge 1$ 即可利用 Grothendieck 对偶算子。

结果
本文通过若干数值算例验证了该理论：

• Gamma/Hankel 矩阵： 对于矩阵 $A_{i,j} = \Gamma(i+j+1/2)/\Gamma(i+j+1)$，新界限（定理 1.1）及相应的有理插值器显著优于基于多项式插值（Little–Reade）和位移结构（Beckermann–Townsend）的现有界限。误差衰减与矩阵的奇异值高度吻合。
• Cauchy 矩阵与张量： 该框架恢复了已知的 Cauchy 矩阵最优结果，并将其扩展到 Cauchy 张量，确认误差受限于底层集合的 Zolotarev 数。
• Log-Cauchy 与 Twisted Hankel 矩阵： 该理论成功地界定了具有对数奇异性和 Hankel 变换的核，其中 Grothendieck 对偶算子涉及积分或特定的权重。
• Beta-Cauchy 矩阵： 该方法应用于由正交多项式基变换产生的矩阵，表明使用 Zolotarev 节点进行有理插值可以达到理论界限。

在所有案例中，可计算的有理逼近（使用 Zolotarev 节点和极点）均达到了理论误差界，且误差衰减是以分离域与奇异集为决定的指数级衰减。

意义
本文声称，该框架为解析核的低秩可逼近性提供了一个比以往方法更精确且通常更紧凑的刻画。通过将焦点从多项式插值（Bernstein 椭圆）转向有理插值（共形模），该理论解释了有理逼近在实践中的卓越表现。Grothendieck 对偶算子的引入允许对具有各种奇异结构（包括 Cauchy 变换无界）的核进行统一处理。此外，证明的构造性特性导致了快速构建这些逼近的算法，其限制仅在于计算特定集合下的最优 Zolotarev 有理函数的能力。这项工作表明，未来通过改进针对离散集合计算 Zolotarev 函数的方法，可以进一步增强这些界限的实际应用价值。