In this paper we approximate high-dimensional functions $f\colon\mathbb T^d\to\mathbb C$ by sparse trigonometric polynomials based on function evaluations. Recently it was shown that a dimension-incremental sparse Fourier transform (SFT) approach does not require the signal to be exactly sparse and is applicable in this setting. We combine this approach with subsampling techniques for rank-1 lattices. This way our approach benefits from the underlying structure in the sampling points making fast Fourier algorithms applicable whilst achieving the good sampling complexity of random points (logarithmic oversampling). In our analysis we show detection guarantees of the frequencies corresponding to the Fourier coefficients of largest magnitude. In numerical experiments we make a comparison to full rank-1 lattices and uniformly random points to confirm our findings.

翻译：在本文中，我们基于函数评估通过稀疏三角多项式逼近高维函数$f\colon\mathbb T^d\to\mathbb C$。最近的研究表明，维度递增的稀疏傅里叶变换（Sparse Fourier Transform，SFT）方法不要求信号完全稀疏，可适用于该设置。我们将此方法与排名-1格点的子采样技术相结合。因此，我们的方法可以从采样点的底层结构中受益，使快速傅里叶算法适用，同时实现随机点（对数过采样）的良好采样复杂性。在我们的分析中，我们展示了与具有最大幅度的傅里叶系数对应的频率的检测保证。在数值实验中，我们与完整的排名-1格点和均匀随机点进行比较以确认我们的发现。