Let $a_1,a_2 \ldots a_n$ be a real-valued sequense with $a_i=O(N^{-1})$. How do I estimate Discrete Fourier Transform (DFT) of this sequence?

$$\hat{a}_{j}=\sum_{r=1}^{K}a_{r}\exp\Bigl(-2\pi ij\frac{r}{K}\Bigr),\qquad K=O(N^\alpha),\quad \alpha<1$$

Can I say that DFT sequence $\operatorname{Re}[\hat{a}_{i}]=O(N^{-1})$?

  • $\begingroup$ Do any of the objects depend on the number $N$? It seems to be floating free. $\endgroup$ – S. Carnahan Jul 24 '10 at 20:59
  • $\begingroup$ $K=O(N^\alpha)$ with $\alpha<1$ $\endgroup$ – vilvarin Jul 24 '10 at 21:06

The answer is no, if you mean an uniform bound in $j$. Here is the example:

Fix $j$ and define $$ a_r = \begin{cases} \frac{1}{N}, & Re(\exp(-2\pi i j r/ K)) \geq 0;\\\ 0, & otherwise.\end{cases} $$ It is than easy to estimate that the number of $a_r = \frac{1}{N}$ is comparable to $K$. Even more is true, one has that the number of $a_r = \frac{1}{N}$ such that $Re(\exp(-2\pi i j r/ K)) \geq \sigma$ is comparable to $K$ for any $\sigma > 0$.

This implies that $$ Re(\hat{a}_j) \geq c N^{1 - \alpha} $$ for some different $c$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.