5
$\begingroup$

I am trying to learn DFT on my own. I have been struggling for a while now around understanding the concept of negative frequencies and notably what happens when $k$ is greater than $N/2$ in the equation:

$$X[k] = {1 \over N} \sum_{n=0}^{N-1} s[n] e^{-i 2 \pi {1\over N} k n}$$

This really frustrates me because I don't see it explained anywhere while it seems to be something so central and probably not that hard to explain!!! So I really need help from someone please, because I am just not progressing because of this.

So where I am at with this. I understand Euler's Formula notably the identity $e^{i\pi} = e^{-i\pi} = -1$. So far I have only being able to suspect that this is the key to my problem. So, if we have $N = 8$ for example when we get $k = {N/2}$ then we gave $k = 4$ which gives $\displaystyle e^{-i2\pi {1 \over N } 4 n} = e^{ -i\pi n} $. So I suspect something happens at this point such as a change in sign somewhere making $e^{-ixxx}$ something like $e^{ixxx}$ but I can't go any further.

Could someone please please try to help me with this, and help me going further?

Thank you very much.

$\endgroup$
3
$\begingroup$

Negative frequencies are best thought of as nothing more than a mathematical curiosity. Historically, Fourier series were sums of sines and cosines. But mathematicians see this as aesthetically repulsive because one must often treat the sine terms and the cosine terms differently. Also, the difference between sines and cosines is a phase shift, and it seems strange that constant phase shifts would be fundamental to this simple idea of breaking functions into periodic components.

But, as you mentioned, we can use Euler's identity $e^{i\omega}=\cos(\omega)+i\sin(\omega)$ and some basic trigonometric laws to find that $$\cos(\omega)=\frac{e^{i\omega}+e^{-i\omega}}{2},$$ $$\sin(\omega)=\frac{e^{i\omega}-e^{-i\omega}}{2i}.$$

Now, mathematically, the exponentials are much simpler, because both the sine and the cosine terms can be shoved into a single type of function. But unfortunately you have to lose the physical meaning of frequency for the negative exponents. I have heard that for some reason the frequencies above the halfway point are unreliable when they are taken from sample data. So the switch into negative frequencies for the DFT, disregarding the upper half, does not result in a loss of physical information.

(I admit I don't understand why completely, but I do know it is a theoretical problem, not just a measurement issue. The key word here is "aliasing" if you want the internet to teach you more about it.)

To answer an implicit question you asked in the middle there: you can do some translation. Euler's identity implies that $s[k]e^{2\pi i}=1$, so $s[k]e^{i(2\pi k/N)} = s[k]e^{i(2\pi k/N-2\pi)}$ which for $k<N$ will give a negative frequency in the exponent. Furthremore, for $k>N/2$ you will get a negative frequency with absolute value at most $i2\pi N/2$, so that will get you the negative values you're looking for.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this long answer. I don't understand in the last paragraph. How can the exponent be negative for $k < N$? $k \over N$ is always smaller or equal to 1, thus $2\pi - 2\pi k /N$ is always positive? Sorry I must be missing something obvious. Thank you again. $\endgroup$ – Marc Ourens Oct 13 '13 at 21:55
  • $\begingroup$ @Marc: Ah, sorry, I meant the terms to be switched around. So not $2\pi - 2\pi k /N$ but $ 2\pi k /N-2\pi$ $\endgroup$ – Eric Stucky Oct 13 '13 at 21:58
  • $\begingroup$ Ah good, could you eventually make the edit please? Also when you say "What is interesting is that for some reason the frequencies above the halfway point are unreliable when they are taken from sample data. So the switch into negative frequencies for the DFT, disregarding the upper half, does not result in a loss of physical information". Sorry I have to say;-) It has to be for something otherwise why computing them? If this wasn't useful then the DFT equation would only compute the N/2 first coefficients? $\endgroup$ – Marc Ourens Oct 13 '13 at 22:01
  • $\begingroup$ @Marc: I really don't know exactly what the issue is, sorry. But I can at least say this, which may be enough for you: if your process is real-valued (as most real processes are!) then the coefficients attached to $\omega$ and $-\omega$ must be complex conjugates. This is an easy consequence of the two formulas I showed you, and perhaps worth working out on your own. So you really do only need the positive frequencies to get all the data. That is why I think of the negative frequencies as a mathematical curiosity :) $\endgroup$ – Eric Stucky Oct 13 '13 at 22:04
0
$\begingroup$

You know I was searching for an answer to a question similar to this myself, because the wikipedia article on Discrete Fourier Transform omits the negative index. I have found many satisfying answers by playing with the formula. There is a tangent section which is not in direct relationship to your question that I think you might find interesting.

In short, negative frequencies (or indices) correspond to counter rotations. If positive frequency goes counterclockwise, then negative frequency goes clockwise.

If you go to the wikipedia page for Fourier Series, the complex version does include negative index.

$$s_N(x) = \sum_{n=-N}^{N} c_n e^{-i2\pi n x/T}$$

I also discovered it is necessary to include negative index for the Discrete Fourier Transform (DFT), take the DFT of a sampled cosine:

$$x_n = \cos (2\pi n/N)$$

And the DFT being what you have:

$$X_k = \sum_{n=0}^{N-1}x_n e^{-i 2\pi k n/N}$$

$$X_k = \sum_{n=0}^{N-1}\cos (2\pi n/N) e^{-i 2\pi k n/N}$$

Using Euler's Formula and the identity:

$$\sum_{n=0}^{N-1} e^{i 2\pi (k-k') n/N}= N\delta_{kk'}$$

You get

$$X_k = \frac{N}{2}(\delta_{1k} + \delta_{-1k})$$

Then if we want the inverse and use the standard formula:

$$x_n = \frac{1}{N}\sum_{k=0}^{N-1}X_k e^{i2\pi kn/N}$$

You can see without the $k=-1$ term in the sum, we don't recover the formula $x_n = \cos(2\pi n/N)$.

So we need negative frequency, but what is it? That is your question.

It's very simple, negative frequency just means clockwise rotations (or just rotations in the opposite of your convention).

It's easy to see if you just look at:

$$\cos(2\pi f t)$$

Where $f$ is frequency and $t$ is time.

Changing $f \rightarrow -f$ is the same as changing $t \rightarrow -t$. If you think about this physically, if time was going backwards, so would the motion of this rotation. It is physical. It is not just a mathematical curiosity, although it certainly is curious in this context.

In my example of $\cos(2\pi n/N)$ we need two counter rotating complex exponentials to cancel out their imaginary parts but retain the real part. This is why it is necessary.

Extending this to negative indices wastes a lot of computational time. There is a clever way of introducing negative indices back into positive ones, which also agrees with our picture of negative frequency corresponding to backwards rotations.

Returning to the calculation of the DFT of $\cos(2\pi n/N)$. We got:

$$X_k = \frac{N}{2}(\delta_{1k} + \delta_{-1k})$$

If we only have indices from $0$ to $N-1$ what is the meaning of $k=-1$ here?

Well imagine you're on a clock with $N$ vertices. Going clockwise amounts to increasing by $+1$. Then if we go counterclockwise it would be $-1$.

Arithmetic on a clock is modular arithmetic. If you imagine a normal clock it's $ a\mod 12$ so if we hit 13, then $13\mod 12 = 1$. Similarly, if we go backwards to $-1$, $-1\mod 12 = 11$. So for an N-clock, $-1\mod N = N-1$. I hope you can see this.

Then we can just map $k = -1 \rightarrow k = N-1$

Let's see how this affects the calculation:

$$X_k = \frac{N}{2}(\delta_{1k} + \delta_{-1k})$$

considering our clock picture, it is now:

$$X_k = \frac{N}{2}(\delta_{1k} + \delta_{(N-1)k})$$

The inverse DFT is:

$$x_n = \frac{1}{N}\sum_{k=0}^{N-1}\frac{N}{2}(\delta_{1k} + \delta_{(N-1)k})e^{i2\pi kn/N}$$

$$x_n = \frac{1}{2}\sum_{k=0}^{N-1}(\delta_{1k} + \delta_{(N-1)k})e^{i2\pi kn/N}$$

$$x_n = \frac{1}{2}(e^{i2\pi n/N} + e^{i2\pi (N-1)n/N})$$

$$x_n = \frac{1}{2}(e^{i2\pi n/N} + e^{-i2\pi n/N}e^{i2\pi N/N})$$

$$x_n = \frac{1}{2}(e^{i2\pi n/N} + e^{-i2\pi n/N}e^{i2\pi })$$

The familiar $e^{i2\pi} = 1$ appears

$$x_n = \frac{1}{2}(e^{i2\pi n/N} + e^{-i2\pi n/N}) = \cos(2\pi n/N)$$

Recovering our formula from before.

The next bunch of lines is a tangent on including negative indices into the calculation. This is just to show that it can be done, but it is completely unnecessary. It may be helpful to see how the kronecker delta identity is defined and proved from our summation formula

Now I hope the rest of what I'm saying is helpful, because this bothers me. The definitions exclude the negative frequency (negative index) components.

The satisfying answer to me is to include negative frequencies and then change the normalization factor on the inverse (that factor of $\frac{1}{N}$)

There is a systematic way of doing this that I can illustrate while also proving the identity:

$$\sum_{k=0}^{N-1} e^{i 2\pi (n-n') k/N}= N\delta_{nn'}$$

Notice I switched the indices from the way it was above. I'm hoping that will make this more transparent to the reader.

First let's take the standard Discrete Fourier Transform and it's inverse and assume that we don't know the normalization factor:

$$X_k = \sum_{n=0}^{N-1}x_n e^{-i 2\pi k n/N}$$

$$x_n = a\sum_{k=0}^{N-1}X_k e^{i2\pi kn/N}$$

You can see $\frac{1}{N} \rightarrow a$

Let's just use the identity and see what we get. The first little trick is to change $n \rightarrow n'$ in our formula for $X_k$. If you don't do this, you get nonsense. The reason why we need to do this is because the index in the Inverse Transform is not necessarily the same index as in the Forward Transform. One index is summed over, and the other index is not.

Plug the first equation into the second.

$$x_n = a\sum_{k=0}^{N-1}(\sum_{n'=0}^{N-1}x_{n'} e^{-i 2\pi k n'/N}) e^{i2\pi kn/N}$$

$$x_n = a\sum_{k=0}^{N-1}\sum_{n'=0}^{N-1}x_{n'} e^{i2\pi k(n-n')/N}$$

Now using the identity we get

$$x_n = aN\sum_{n'=0}^{N-1}x_{n'} \delta_{nn'}$$

and $\delta_{nn'} =1$ only when $n=n'$ and zero otherwise by its definition. Therefore:

$$x_n = aNx_n \implies a = \frac{1}{N}$$

What if we want to now extend the definition to negative index? Computationally, I understand this is not a great idea since it doubles the amount of computations, but theoretically I think it is satisfying.

Suppose we took the sum from $-R$ to $N-1$. This will no longer make the number of samples $N$ but a new number $P=N+R$. You can convince yourself of this by counting from $-R$ to $N-1$. We pass over 0 so we count $R$ plus $1$ for the count of zero plus $N-1$ for the rest. The total is then as I stated: $P=N+R$

Then we have these pairs of formula:

$$X_k = \sum_{n'=-R}^{N-1}x_{n'}e^{-i 2\pi k n'/P}$$

$$x_n = a\sum_{k=-R}^{N-1}X_k e^{i2\pi kn/P}$$

Plugging the first into the second gives

$$x_n = a\sum_{k=-R}^{N-1}(\sum_{n'=-R}^{N-1}x_{n'}e^{-i 2\pi k n'/P}) e^{i2\pi kn/P}$$

Let's, as before, concentrate on the sum over $k$. We want to prove the identity for the discrete sum of complex exponentials. We can change the order of the sums to do this (something I'll let you figure out for yourself since I'm already writing so much).

$$ \sum_{k=-R}^{N-1}e^{-i 2\pi k n'/P} e^{i2\pi kn/P}$$

$$ \sum_{k=-R}^{N-1}e^{i 2\pi k (n-n')/P} $$

We omit $x_{n'}$ because in the $k$ sum this is just a constant. We keep the $n'$ in the exponential because we want to ask what happens when $n' = n$ and $n' \neq n$

First if $n'=n$ then the complex exponential is of the form $e^{0} = 1$. Then the sum is just:

$$\sum_{k=-R}^{N-1}1 $$

And since the sum goes from $-R$ to $N-1$ we sum $1$ $P$ times.

$$\sum_{k=-R}^{N-1}1 = P $$

If $P \rightarrow N$ then $R \rightarrow 0$ and we recover that familiar factor of $N$ from before.

Now if $n'\neq n$ we have to do more work

$$ \sum_{k=-R}^{N-1}e^{i 2\pi k (n-n')/P} $$

First let's re-index the sum. We can set $k\rightarrow k-R$ and then the new $k$ will start from $0$ and go to $P-1$ (much like we had before). You can see if $k=0$ then $k-R = -R$ and if $k=P-1$ then $k-R = P-1-R = N-1$. Exactly what we had before.

$$ \sum_{k=0}^{P-1}e^{i 2\pi (k-R) (n-n')/P} $$

Let's factor out the part of the exponential that doesn't contain $k$. To make things a bit neater I'm going to define $n-n' = \Delta n$ so the difference in the two integers which we know in our current case is not $0$.

$$ \sum_{k=0}^{P-1}e^{i 2\pi \Delta n(k-R)/P} $$

$$ \sum_{k=0}^{P-1}e^{i 2\pi( \Delta n(k)-\Delta n(R))/P} $$

$$ e^{-i 2\pi \Delta n R/P}\sum_{k=0}^{P-1}e^{i 2\pi \Delta n k/P} $$

Now we luckily have a formula for a finite geometric series:

$$\sum_{l=0}^{L-1}r^l = \frac{1-r^L}{1-r}$$

We will just copy what we have into that

$$ e^{-i 2\pi \Delta n R/P}(\frac{1-e^{(-i 2\pi \Delta n /P)P}}{1-e^{-i 2\pi \Delta n R/P}} )$$ $$ e^{-i 2\pi \Delta n R/P}(\frac{1-e^{-i 2\pi \Delta n }}{1-e^{-i 2\pi \Delta n /P}} )$$

If you focus on the numerator you see the part of the exponent $\Delta n$ is always an integer since the difference of two integers is an integer. Thus

$$e^{-i 2\pi \Delta n} = 1$$

Looking at the numerator of our formula, we then get $1-1 =0$. Thus when $n'\neq n$ or equivalently when $\Delta n \neq 0$

$$ e^{-i 2\pi \Delta n R/P}(\frac{1-e^{-i 2\pi \Delta n }}{1-e^{-i 2\pi \Delta n /P}} ) = 0$$

We don't have to worry about the denominator since the greatest $\Delta n$ can be is $P-1$, so $(P-1)/P <1$ and will not make the denominator $0$. You can check yourself. We also already assumed $\Delta n \neq 0$ so that can't happen either. You could show an alternative proof at this stage for $\Delta n = 0$ to agree with what we had before (L'hopital).

We can then sum up our formula using the kronecker delta symbol $\delta_{nn'}$ which, once again, is 1 if $n=n'$ and 0 otherwise.

$$ \sum_{k=-R}^{N-1}e^{i 2\pi k (n-n')/P} = P\delta_{nn'}$$

It is the kronecker delta times the length of the interval which in this case is $P$.

For completeness, we can do our proof again for the normalization factor

$$x_n = a\sum_{k=-R}^{N-1}(\sum_{n'=-R}^{N-1}x_{n'}e^{-i 2\pi k n'/P}) e^{i2\pi kn/P}$$ $$x_n = a\sum_{n'=-R}^{N-1}x_{n'}P\delta_{nn'}$$

$$x_n = a x_n P$$

Therefore $a = \frac{1}{P}$ in this case.

The point of this calculation is to show that we can use any integer indices we want as long as we use the correct normalization factor which will be the the total number of data points.

"End of Tangent"

| cite | improve this answer | |
$\endgroup$

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.