Optimal Extrapolation Bounds for Sparse Fourier Sums

技术摘要：稀疏傅里叶和的最优外推界限

问题陈述
本文研究了对于任意实数频率的 $k$-稀疏傅里叶和的确定性外推问题，特别是在不存在频率间隔假设的情况下。给定一个信号 $g(t) = \sum_{j=1}^k v_j e^{i\lambda_j t}$，已知其在观测区间 $[-1, 1]$ 上的 $L^2$ 能量，核心问题是：在已知观测区间外的点 $x > 1$ 处，$|g(x)|$ 最大可以达到多少？

该问题在“聚类机制”（clustered regime）中至关重要，即多个频率可能比观测窗口长度的倒数还要接近。在这种极限情况下，信号趋向于 $k-1$ 次代数多项式的空间。Chen 和 Price (ICALP 2019) 此前的研究提供了一个外推界限，其指数增长率为 $\exp(O(k^2 \log k \cdot \delta))$，其中 $x = 1+\delta$。然而，作者指出，多项式增长（切比雪夫多项式）的经典极值示例表明，存在更紧凑的 $\exp(\Theta(k\sqrt{\delta}))$ 界的限。本文旨在确定任意 $k$ 项傅里叶和是否遵循这种更精确的切比雪夫尺度界限。

方法论
作者开发了一种全新的证明技术，将端点外推问题转化为单侧加权问题，从而避免了标准局部传播论证以及黑盒 Turán–Nazarov 不等式的局限性。

1. 向加权半直线的转换： 证明过程始于将信号 $g(t)$ 转换为 $F(u) = g(1-u)$，将观测区间 $[-1, 1]$ 映射到 $[0, 2]$，并将外推点 $1+\delta$ 映射到 $-\delta$。随后将该问题与加权半直线范数 $\int_0^\infty |F(u)|^2 e^{-\alpha u} du$ 进行比较。
2. Hardy 空间与 Takenaka–Malmquist 基： 通过令 $H(u) = e^{-\alpha u/2}F(u)$ 来吸收权重，使信号表示为右半平面内的衰减指数之和。作者利用 Hardy 空间 $H^2(\mathbb{C}^+)$ 并使用 Takenaka–Malmquist 系统构建正交基。该基允许对信号进行稳定的展开，而无需反转病态的范德蒙德矩阵（Vandermonde matrices）。
3. Laguerre 多项式极大值函数： 一个关键的技术步骤是限制这些基函数在负点（外推区域）的评估值。作者证明了基函数在 $-\delta$ 处的量级受 Laguerre 多项式 $L_m(-\alpha \delta)$ 的支配。通过利用代数界限 $L_m(-y) \leq e^{2\sqrt{my}}$，他们导出了对外推距离的平方根依赖关系。
4. 无穷-有限范围不等式： 为了将加权半直线范数关联回观测到的有限区间 $[0, 2]$，作者采用了 Erdélyi 的无穷-有限范围不等式，该不等式允许将积分的尾部由与 $k/\alpha$ 成比例的有限段积分来界定。
5. 外部机制与下界： 对于 $x \geq 2$，使用了单独的 Turán 型外推论证。为了证明最优性，作者构造了一系列收敛于切比雪夫多项式的 $k$-稀疏傅里叶和，证明了所推导的上界在 $k$ 的多项式因子范围内是紧致的。

主要贡献与结果
本文确立了以下最优外推定理：

• 主定理 (Theorem 1.1)： 对于每个 $k$-稀疏傅里叶和 $g(t)$ 以及每个 $x \geq 1$：
  $$|g(x)| \lesssim k^2 \exp\left(3\sqrt{2} k \operatorname{arcosh} x\right) \|g\|_{L^2[-1,1]}$$
  在端点机制下（$x = 1+\delta$ 且 $0 \leq \delta \leq 1$），该式精炼为：
  $$|g(1+\delta)| \lesssim k \exp\left(3\sqrt{2} k \sqrt{\delta}\right) \|g\|_{L^2[-1,1]}$$
• 最优性： 证明了指数缩放 $\exp(\Theta(k\sqrt{\delta}))$ 在绝对常数和 $k$ 的多项式因子意义下是优化的。这解决了 Chen 和 Price 提出的差异，确认了任意稀疏傅里叶和并不会表现出此前估计的较慢的 $k^2 \log k$ 增长。
• 算法改进：
  • 聚类频率恢复： 作者构造了一个直接匹配切比雪夫包络的带限滤波器，消除了先前算法中对幂律增长参数 $S$ 的需求。这使得加法簇中心分辨率从 $\Delta + e^{O(k^3/T)}$ 提升至 $\Delta + O(k^2/T)$，同时保持了样本复杂度。
  • 外推主动回归： 这些结果为稀疏傅里叶特征空间提供了关于外部杠杆得分（leverage scores）和转移常数的精确界限。论文表明，从训练区间到外部区域 $X_\Delta$ 的最坏情况 $L^2$ 转移常数按 $\exp(\Theta(k\sqrt{\Delta}))$ 缩放。这意味着当 $k\sqrt{\Delta} = O(\log k)$ 时，域内主动回归保证仅以多项式开销即可转移到外部预测。

意义
本文声称，这些结果提供了针对稀疏傅里叶和的首个精确、无间隔假设的外推界限。通过识别内在的切比雪夫尺度增长剖面，这项工作消除了算法设计中对松散幂律替代物的需求。这使得聚类频率恢复算法的分辨率提升了一个 $k$ 倍因子，并确立了稀疏傅里叶模型外推的基本极限，表明基于域内 $L^2$ 误差的黑盒推论，其真正的极限是“切比雪夫壁垒”。