论文标题
稀疏的傅立叶变换在许多变量的功能的快速和低内存近似中的等级-1晶格上
Sparse Fourier Transforms on Rank-1 Lattices for the Rapid and Low-Memory Approximation of Functions of Many Variables
论文作者
论文摘要
我们考虑在$ d $维圆环上近似函数的快速，准确的算法，$ f：\ mathbb {t}^d \ rightArrow \ rightArrow \ mathbb {c} $，在傅立叶基础上是稀疏（或可压缩的）。特别是，假设$ f $，$ \ {c _ {\ bf k}（f）\} _ {{\ bf k} \ in \ mathbb {z}^d} $集中在A有限的$ i \ subset \ subbb {z z}^d $ so 英石。 |ω| = s} \ left \ | f - \ sum _ {{\ bf k} \ inω} c _ {\ bf k}（f）我们旨在确定一个接近最小的子集$ω\子集i $，并准确近似相关的傅立叶系数$ \ {c _ {\ bf k}（f）\} _ {{\ bf k} \ inω} $，尽可能迅速。我们使用$ o（s^2 d \ log^c（| i |））$ - 时间/内存和$ o（s d \ log^c（| i |））$ - 时间/内存分别提出确定性和随机算法。最关键的是，本文提出的所有方法都达到了这些运行时，同时满足了理论最佳$ S $ term近似保证的保证，这些保证可以保证其数值的准确性和对一般功能的噪声的鲁棒性。 这些是通过修改几种一维稀疏傅立叶变换（SFT）方法来实现的，以沿重建给定频率集$ i $的重建级别1晶格的函数来迅速识别近乎最小的子集$ω\子集I $，而无需在其发电室以外的晶格上使用任何内容。这需要新的快速和低内存频率识别技术，能够在$ \ mathbb {z}^d $中快速恢复矢量值频率，而不是单变量设置中的简单整数频率。提出和分析了两种不同的策略，每个策略的精度与计算速度和内存权衡不同。
We consider fast, provably accurate algorithms for approximating functions on the $d$-dimensional torus, $f: \mathbb{ T }^d \rightarrow \mathbb{C}$, that are sparse (or compressible) in the Fourier basis. In particular, suppose that the Fourier coefficients of $f$, $\{c_{\bf k} (f) \}_{{\bf k} \in \mathbb{Z}^d}$, are concentrated in a finite set $I \subset \mathbb{Z}^d$ so that $$\min_{Ω\subset I s.t. |Ω| =s } \left\| f - \sum_{{\bf k} \in Ω} c_{\bf k} (f) e^{ -2 πi {\bf k} \cdot \circ} \right\|_2 < ε\|f \|_2$$ holds for $s \ll |I|$ and $ε\in (0,1)$. We aim to identify a near-minimizing subset $Ω\subset I$ and accurately approximate the associated Fourier coefficients $\{ c_{\bf k} (f) \}_{{\bf k} \in Ω}$ as rapidly as possible. We present both deterministic as well as randomized algorithms using $O(s^2 d \log^c (|I|))$-time/memory and $O(s d \log^c (|I|))$-time/memory, respectively. Most crucially, all of the methods proposed herein achieve these runtimes while satisfying theoretical best $s$-term approximation guarantees which guarantee their numerical accuracy and robustness to noise for general functions. These are achieved by modifying several one-dimensional Sparse Fourier Transform (SFT) methods to subsample a function along a reconstructing rank-1 lattice for the given frequency set $I$ to rapidly identify a near-minimizing subset $Ω\subset I$ without using anything about the lattice beyond its generating vector. This requires new fast and low-memory frequency identification techniques capable of rapidly recovering vector-valued frequencies in $\mathbb{Z}^d$ as opposed to simple integer frequencies in the univariate setting. Two different strategies are proposed and analyzed, each with different accuracy versus computational speed and memory tradeoffs.
