# Estimation of DFT

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})$?

• Do any of the objects depend on the number $N$? It seems to be floating free. – S. Carnahan Jul 24 '10 at 20:59
• $K=O(N^\alpha)$ with $\alpha<1$ – 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$.