0
$\begingroup$

The Discrete Fourier Transform (DFT) of a function $u:[0,2\pi] \to \mathbb R$ sampled over $N$ equidistant points $\theta_j = 2\pi j/N,\, j = 0, \dots, N-1,$ is defined by

$$ \tilde U_k = \frac1N \sum_{j=0}^{N-1} u_j e^{-ik\theta_j}\,, \qquad \text{where } k \in [k]_N \in \frac{\mathbb Z}{N\mathbb Z}\,. $$

The indices $k$ could go from $-N/2+1$ to $N/2$ in one convention and from $0$ to $N-1$ in another. Since $\tilde U_{k + N} = \tilde U_k\,, \forall k \in \mathbb Z$, the negative frequencies can be pushed all the way over to the other side of the positive frequencies to get the all-positive convention. This means that the negative frequencies $k \in \{ -1, -2, \dots, -N/2 + 1\}$ in one convention map to the frequencies $k + N \in \{N-1, N-2, \dots, N/2 + 1\}$ in the other convention.

We know that the derivative of the function $u$ can be calculated as follows:

$$ u'(\theta) = \sum_{k=-N/2 + 1}^{N/2} ik\, \tilde U_k e^{ik\theta}\,. $$

This would mean that in the all-positive convention,

$$ u'(\theta) = \sum_{k=0}^{N/2} ik\, \tilde U_k e^{ik\theta} + \sum_{k = N/2 + 1}^{N-1} i(k-N)\, \tilde U_k e^{ik\theta} \,. $$

Is that correct? If yes, why is it that the spectral derivative requires the use of negative frequencies? What goes wrong in the claim that

$$ u'(\theta) = \sum_{k=0}^{N-1} ik\, \tilde U_k e^{ik\theta}\,? $$

$\endgroup$
0
$\begingroup$

There is no requirement, it is a matter of choice.

Some conceptual clarity is required. A sequence of sampled points does not have a derivative. Derivatives come from continuous functions.

If you treat the inverse DFT definition as a continuous function, the result is a continuous interpolation function that will pass through all your sampled points. Choosing different ranges (could be 6N to 7N-1 if you wanted) yields different interpolation functions each being differentiable.

This thread should give you some insight:

How to get Fourier coefficients to draw any shape using DFT?

The "simplest" or "most natural" range is using the negative frequencies, and if you have an even number of bins, the Nyquist bin should be split in half, one positive and one negative.

$\endgroup$
  • $\begingroup$ I am sorry I fail to understand why the choice of notation would be called a convention if different choices would give different results. For sure, I can have different interpolations through a set of sampled points, but if the points are close enough, the interpolations should not differ much and should give close enough answers, for example close to what I would expect to get from a finite difference algorithm. Why should one choice of frequencies give a different answer from that given by another choice? Or, do they not? Are the answers for both notations almost the same? Thanks. $\endgroup$ – Nanashi No Gombe Oct 10 at 13:44
  • $\begingroup$ @NanashiNoGombe This is not true: "but if the points are close enough, the [DFT based] interpolations should not differ much and should give close enough answers" Check out the "fluffy cloud" graphics in my answer in the referenced thread. The "most bandlimited" DFT based solution, i.e. simplest and smoothest, is the zero centered one. There are many other formulas for approximating "the derivative" at a point in a sequence of samples. $\endgroup$ – Cedron Dawg Oct 10 at 14:43
  • $\begingroup$ Thanks, I’ll check your linked answer. So, to summarise, are both formulas correct? $\endgroup$ – Nanashi No Gombe Oct 10 at 14:46
  • $\begingroup$ @NanashiNoGombe You're welcome. Actually no, the compound one isn't. The coefficient needs to match the exponent. The only thing at play is the range. In fact, for any bin, you can select any of the aliases for that bin, and you will still get an interpolation function which passes through each point. $\endgroup$ – Cedron Dawg Oct 10 at 14:53

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.