[FIXED] Control number of fft coefficients

Issue

I have a signal of 5000 points x and y When I use the discrete fourier transform manually, it is possible to create a list of coefficients controlling the number of coefficients, and the more coefficients, the greater the approximation of the original signal.

In the example below there is a signal of 5000 points that after going through the DFT generated a list with 201 coefficients.

But when using the fft() function I can't control the amount of coefficients.

Is there any way to use numpy or scipy, or their fft functions to generate the same 201 coefficients, instead of generating 5000 coefficients?

import matplotlib.pyplot as plt
import numpy as np
from math import tau
from scipy.integrate import quad_vec
from scipy.fft import fft

def f(t, t_list, x_list, y_list):
    return np.interp(t, t_list, x_list + 1j*y_list)

N = 5000
t_list = np.linspace(0, 2*np.pi, N)

r = (((0.0*np.pi<=t_list) * (t_list<=0.5*np.pi)) * 1/np.cos(t_list-0.25*np.pi) +
    ((0.5*np.pi<t_list) * (t_list<=1.0*np.pi)) * 1/np.cos(t_list-0.75*np.pi) +
    ((1.0*np.pi<t_list) * (t_list<=1.5*np.pi)) * 1/np.cos(t_list-1.25*np.pi) +
    ((1.5*np.pi<t_list) * (t_list<=2.0*np.pi)) * 1/np.cos(t_list-1.75*np.pi))

# create de signal a square form
x_list, y_list = np.cos(t_list) * r, np.sin(t_list) * r

fig, ax = plt.subplots(figsize=(5, 5))
ax.set_aspect('equal')
ax.plot(x_list, y_list)

print('x length list: ', len(x_list)) #5000 points
print('y length list: ', len(y_list)) #5000 points

order = 100 # -order to order i.e -100 to 100
# you can change the order to get proper figure
# too much is also not good, and too less will not produce good result

print("generating coefficients ...")
# lets compute fourier coefficients from -order to order
c = []

# we need to calculate the coefficients from -order to order
for n in range(-order, order+1):
    # calculate definite integration from 0 to 2*PI
    # formula is given in readme
    coef = 1/tau*quad_vec(lambda t: f(t, t_list, x_list, y_list)*np.exp(-n*t*1j), 0, tau, limit=100, full_output=1)[0]
    c.append(coef)

print("completed generating coefficients.")

c = np.array(c)

print('c length list: ', len(c))

# convert x and y to complex number
z = x_list + 1j*y_list

#get coeff of all element of list
coeff_fft = fft(z)

print('coeff_fft length list: ', len(coeff_fft))

OUTPUT

x length list:  5000
y length list:  5000
generating coefficients ...
completed generating coefficients.
c length list:  201
coeff_fft length list:  5000

Solution

The DFT of N samples has N values. Any less and the transform wouldn’t be reversible. But of course you can compute individual elements of the transform.

The FFT (which you use when you call fft()) is a fast algorithm to compute the DFT. It is fast because it computes the full transform, not individual elements.

I am not aware of a function in a standard library that computes individual values of the DFT. But as you’ve shown, it is easy to write such a function. So either manually compute those 201 values as you do now, or compute the full DFT using fft() and pick out the values you need. Which one is faster depends on how many values you need and how many samples you have.

Answered By - Cris Luengo