Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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