MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

Your Answer


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.