  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 $\epsilon$ 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(\epsilon^{-1} k \log(n/\delta))$ Fourier measurements, runs in
$O(\epsilon^{-1} k \log(n/\delta))$ time and outputs a vector $x'$ such that
$\| ( x' - \widehat{x} )_S \|_2^2 \leq \epsilon \| \widehat{x}_{\bar{S}} \|_2^2
+ \delta \| \widehat{x} \|_1^2 $ holds with probability of at least $9/10$.
