论文标题
$ o（k \ log n）$ time fourier set查询算法
An $O(k\log n)$ Time Fourier Set Query Algorithm
论文作者
论文摘要
在许多研究领域，傅立叶变换是一个广泛研究的问题。它在机器学习，信号处理，压缩感测等方面有许多应用。在许多实际应用中，近似的傅立叶变换就足够了，我们只需要在坐标子集上进行傅立叶变换即可。给定一个向量$ x \ in \ mathbb {c}^{n} $，近似参数$ε$和查询集$ s \ subset [n] size $ k $的$ s $ k $，我们建议算法来计算近似傅立叶变换结果$ x'$ wht $ o o（sum o o o o o o o o o（> aim MOUT）$ o（ε^{ε^{ε^{ε^{ε^a/untuers） $ o（ε^{ - 1} k \ log（n/δ））$时间并输出vector $ x'$，这样$ \ | （x' - \ wideHat {x}）_s \ | _2^2 \leqε\ | \ wideHat {x} _ {\ bar {s}}} \ | _2^2 +δ\ | \ wideHat {x} \ | _1^2 $保持至少$ 9/10 $。
Fourier transformation is an extensively studied problem in many research fields. It has many applications in machine learning, signal processing, compressed sensing, and so on. In many real-world applications, approximated Fourier transformation is sufficient and we only need to do the Fourier transform on a subset of coordinates. Given a vector $x \in \mathbb{C}^{n}$, an approximation parameter $ε$ and a query set $S \subset [n]$ of size $k$, we propose an algorithm to compute an approximate Fourier transform result $x'$ which uses $O(ε^{-1} k \log(n/δ))$ Fourier measurements, runs in $O(ε^{-1} k \log(n/δ))$ time and outputs a vector $x'$ such that $\| ( x' - \widehat{x} )_S \|_2^2 \leq ε\| \widehat{x}_{\bar{S}} \|_2^2 + δ\| \widehat{x} \|_1^2 $ holds with probability of at least $9/10$.
