论文标题
在高维的任意频率候选设置的样品有效稀疏FFT
A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
论文作者
论文摘要
在本文中，提出了一种均值时间算法，用于重建功能，这在高空间维度中仅由潜在的大型傅立叶基函数组中所代表，这是一种所谓的高维稀疏快速快速傅立叶变换。与许多其他此类算法相反，我们的方法适用于任意候选人集，并且不对候选人集做出其他结构假设。我们的转换在样本复杂性的缩放方面可在此类一般框架上可用的其他方法显着改善。我们的算法基于用随机发电机沿多个级别1晶格的函数采样。 结合尺寸提示方法，我们的方法产生了稀疏的傅立叶变换，其计算复杂性仅在尺寸中温和增长，因此即使在高维度中也可以有效地计算。我们的理论分析表明，任何傅立叶$ S $ -SPARSE功能都可以以很高的可能性准确地重建。该保证是通过几项数值测试补充的，这些测试证明了精确稀疏的情况以及可压缩案例的高效率和多功能性。
In this paper a sublinear time algorithm is presented for the reconstruction of functions that can be represented by just few out of a potentially large candidate set of Fourier basis functions in high spatial dimensions, a so-called high-dimensional sparse fast Fourier transform. In contrast to many other such algorithms, our method works for arbitrary candidate sets and does not make additional structural assumptions on the candidate set. Our transform significantly improves upon the other approaches available for such a general framework in terms of the scaling of the sample complexity. Our algorithm is based on sampling the function along multiple rank-1 lattices with random generators. Combined with a dimension-incremental approach, our method yields a sparse Fourier transform whose computational complexity only grows mildly in the dimension and can hence be efficiently computed even in high dimensions. Our theoretical analysis establishes that any Fourier $s$-sparse function can be accurately reconstructed with high probability. This guarantee is complemented by several numerical tests demonstrating the high efficiency and versatile applicability for the exactly sparse case and also for the compressible case.
