# Calculating a non-uniform discrete Fourier transform

According to Wikipedia, a non-uniform Fourier transform can be calculated as follows:

where are sample points and are frequencies.

Now, say I have samples $$x_n$$ taken at times $$t_n$$. To get my $$p_n$$ values, presumably I just scale the times of my samples between 0 and 1, like so:

$$p_n = \frac{t_n - \min(t_n)}{\max(t_n) - \min(t_n)}$$

All I need now for the calculation is $$f_k$$, which I'm a bit confused about.

1. What value(s) should $$f_k$$ assume?
2. Or does specifying $$f_k$$ somehow define the frequency bin associated with $$X_k$$? If so, how?
3. If I set $$f_k$$ as a constant, say $$\alpha$$, then what value would the $$k^\text{th}$$ frequency bin assume?

1. What value(s) should $$f_k$$ assume?

Depends on what you're interested in. Say you've got a N-point NUDFT, and you're interested at frequencies that are distributed as $$f_k = k^2$$. Clearly, $$f_k$$'s are not consecutive and hence a traditional N-FFT would not yield the desired frequency spectrum.

2. Or does specifying $$f_k$$ somehow define the frequency bin associated with $$X_k$$? If so, how?

This is exactly the point. You're interested in, say $$f_k=k^2$$, so why won't I just pick my $$f_k$$'s to be those frequencies.

3. If I set $$f_k$$ as a constant, say $$\alpha$$, then what value would the $$k^\text{th}$$ frequency bin assume?

This is not an interesting case as you'd get $$X_1 = \ldots = X_n = \sum\limits_{n=0}^{N-1} x_n e^{- 2 \pi i p_n \alpha}$$

• Thanks, Ahmad. Very insightful. A quick follow up for clarification. Is $f_k$ in Hz, because it seems to be nondimensional? Or is it relative to the duration considered (i.e., $\max(t_n) - \min(t_n)$)? And does it refer to the mid-point of the frequency bin?
– Dan
Nov 8, 2019 at 13:50