The nonumiform discrete Fourier transform is defined by the following formula: $${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-2\pi ip_{k}\omega _{n}},\quad 0\leq k\leq N-1,}$$ where $p_0,...p_{N-1}\in[0,1]$ are so called sample points and ${\displaystyle \omega _{0},\ldots ,\omega _{N-1}\in [0,N]}$ are frequencies.

I now want to use the formula to calculate the Fourier series at so called nonequispaced points. That means, my points have a variable space between each other. An example: demonstrating graph

There exist three types of nonuniform discrete Fourier transforms. For my use case, the second type (NUDFT-II) seems to fit the best, which uses uniform frequencies with $\omega_n = n$ and nonuniform sample points $p_k$, as it evaluates "a Fourier series at nonequispaced points" (Wikipedia).

I could, however, not find any explanation regarding how to choose the sample points $p_k$, or what those points actually stand for.

In the discrete Fourier transform $p_k$ equals $n/N$. Does this mean, that in the nonuniform discrete Fourier trasnform of type II it equals the distance of the current point $n$ to the beginning of the original signal divided by the length of the signal, hence describing "the percent of the time we've gone through" (as described here)?

Edit: This theory is backed by this definition: $$P(m) = \sum _{n=0}^{N-1}p_ne^{-j\frac{2\pi}{T}mt_n}$$ Which can be translated to use the same variable names: $$X_k = \sum _{n=0}^{N-1}x_ne^{-2\pi i\frac{t_n}{T}k}$$

Hence $p_k$ would equal $\frac{t_n}{T}$ and $\omega$ would equal $k$. This however is a little bit weird, as the Wikipedia article stated that $\omega$ should equal $n$. Is this a mistake of the Wikipedia article? Actually I think it makes much more sense with $k$. But can I assume that my assumption was right and $p_k$ does equal $\frac{t_n}{T}$?

However, this causes another problem: For which frequencies does the transform has to be applied? With the normal Fourier transform it's generally from $0$ up to $N-1$. This doesn't seem to work here though. Do I now have to calculate the values for the frequencies from $t_0$ to $t_{N-1}$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.