Calculating a non-uniform discrete Fourier transform

Question

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?

Many thanks in advance.

Answer 1

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}$$