numpy.fft.fft not computing dft at frequencies given by numpy.fft.fftfreq?

Question

This is a mathematical question, but it is tied to the numpy implementation, so I decided to ask it at SO. Perhaps I'm hugely misunderstanding something, but if so I would like to be put straight.

numpy.ftt.ftt computes DFT according to equation:

numpy.ftt.fftfreq is supposed to return frequencies at which DFT was computed.

Say we have:

x = [0, 0, 1, 0, 0]
X = np.fft.fft(x)
freq = np.fft.fftfreq(5)

Then for signal x, its DFT transformation is X, and frequencies at which X is computed are given by freq. For example X[0] is DFT of x at frequency freq[0], X[1] is DFT of x at frequency freq[1], and so on.

But when I compute DFT of a simple signal by hand with the formula quoted above, my results indicate that X[1] is DFT of x at frequency 1, not at freq[1], X[2] is DFT of x at frequency 2, etc, not at freq[2], etc.

As an example:

In [32]: x
Out[32]: [0, 0, 1, 0, 0]

In [33]: X
Out[33]: 
array([
    1.00000000+0.j, 
    -0.80901699-0.58778525j,
    0.30901699+0.95105652j,  0.30901699-0.95105652j,
    -0.80901699+0.58778525j])

In [34]: freq
Out[34]: array([ 0. ,  0.2,  0.4, -0.4, -0.2])

If I compute DFT of above signal for k = 0.2 (or freq[1]), I get X at freq = 0.2: 0.876 - 0.482j, which isn't X[1].

If however I compute for k = 1 I get the same results as are in X[1] or -0.809 - 0.588j.

So what am I misunderstanding? If numpy.fft.fft(x)[n] is a DFT of x at frequency n, not at frequency numpy.fft.fttfreq(len(x))[n], what is the purpose of numpy.fft.fttfreq?

Answer 1

The DFT is a dimensionless basis transform or matrix multiplication. The output or result of a DFT has nothing to do with frequencies unless you know the sampling rate represented by the input vector (samples per second, per meter, per radian, etc.)

You can compute a Goertzel filter of the same length N with k=0.2, but that result isn't contained in an DFT or FFT result of length N. A DFT only contains complex Goertzel filter results for integer k values. And to get from k to the frequency represented by X[k], you need to know the sample rate.

Answer 2

1. Yours is not a SO question

2. You wrote

   If I compute DFT of above signal for k = 0.2 .

   and I reply "You shouldn't"... the DFT can be meaningfully computed only for integer values of k.

3. The relationship between an index k and a frequency is given by f_k = k Δf or, if you prefer circular frequencies, ω_k = k Δω where Δf = 1/T and Δω = 2πΔf, T being the period of the signal.

4. The arguments of fftfreq are a bit misleading... the required one is the number of samples n and the optional argument is the sampling interval, by default d=1.0, but at any rate T=n*d and Δf = 1/(n*d)

   >>> fftfreq(5) # d=1
   array([ 0. ,  0.2,  0.4, -0.4, -0.2])
   >>> fftfreq(5,2)
   array([ 0. ,  0.1,  0.2, -0.2, -0.1])
   >>> fftfreq(5,10)
   array([ 0.  ,  0.02,  0.04, -0.04, -0.02])
   

   and the different T are 5,10,50 and the respective df are -.2,0.1,0.02 as (I) expected.

5. Why fftfreq doesn't simply require the signal's period? because it is mainly intended as an helper in demangling the Nyquist frequency issue.
   As you know, the DFT is periodic, for a signal x of length N you have that DFT(x,k) is equal to DFT(x,k+mN) where m is an integer.
   This imply that there are only N/2 positive and N/2 negative distinct frequencies and that, when N/2<k<N, the frequency that must be associated with k in the most meaningful way is not k df but (k-N) df.
   To perform this, fftfreq needs more information that the period T, hence the choice of requiring n and computing df from an assumption on sampling interval.

Answer 3

I think that because the values in the array returned by the numpy.fft.fttfreq are equal to the (k/n)*sampling frequency.

The frequencies of the dft result are equal to k/n divided by the time spacing, because the periodic function's period's amplitude will become the inverse of the original value after fft. You can consider the digital signal function is a periodic sampling function convoluted by the analog signal function. The convolution in time domain means multiplication in frequency domain, so that the time spacing of the input data will affect the frequency spacing of the dft result and the frequency spacing's value will become the original one divided by the time spacing. Originally, the frequency spacing of the dft result is equal to 1/n when the time spacing is equal to 1. So after the dft, the frequency spacing will become 1/n divided by the time spacing, which eqauls to 1/n multiplied by the sampling frequency.

To calculate that, the numpy.fft.fttfreq has two arguments, the length of the input and time spacing, which means the inverse of the sampling rate. The length of the input is equal to n, and the time spacing is equal to the value which the result k/n divided by (Default is 1.)

I have tried to let k = 2, and the result is equal to the X[2] in your example. In this situation, the k/n*1 is equal to the freq[2].