1
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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