Fast Fourier Transform – An Intuition

One of my favorite youtube channels, 3Blue1Brown, has a great video on the intuition of the FFT. Check the video above.

Below Python code to implement that intuition:

# https://youtu.be/spUNpyF58BY

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sns

sns.set()

def cart2pol(x, y):
    rho = np.sqrt(x**2 + y**2)
    phi = np.arctan2(y, x)
    return(rho, phi)

def pol2cart(rho, phi):
    x = rho * np.cos(phi)
    y = rho * np.sin(phi)
    return(x, y)

t = np.arange(0,5,0.01) # time 

amp_offset = 1 # to avoid negative y-values

freq = 3 #frequency of the signal we want to identify

df = pd.DataFrame({'t' : t,
                  'amp' : amp_offset + np.sin(freq*t*2*np.pi)})

df.plot(x='t',y='amp')
plt.ylabel('amplitude')
plt.xlabel('time')

# polar plot with the same wrapping freq. as the signal

plt.figure(figsize=(18,12))
plt.polar(df['t'] * freq * 2 * np.pi,df['amp'])

ax = plt.gca()

ax.set_theta_zero_location('N')
ax.set_theta_direction(-1)

# wrap data on circles with frequency Hz

def plot_g(df,Hz,freq,ax):
    title = 'True Signal Frequency: {} Wrapping Frequency; {}'.format(freq,Hz)
    
    cartesian = pd.DataFrame(pol2cart(df['amp'],df['t'] * Hz * 2 * np.pi)).T
    cartesian.columns = ['y','x']
    ax.set_title(title)
    ax.plot(cartesian['x'],cartesian['y'],'o--')
    ax.plot(cartesian['x'].mean(),0,'o',color='orange')

# same wrapping frequency as the signal
ax = plt.gca()
plot_g(df,freq,freq,ax)

# plots with different wrapping frequencies. Note that all wrap.freq's but the correct one
# have their centre of mass (the orange dot) at origo. 

fig,axes = plt.subplots(2,3,figsize=(18,12))

plot_g(df,1,freq,axes[0,0])
plot_g(df,2,freq,axes[0,1])
plot_g(df,3,freq,axes[0,2])
plot_g(df,4,freq,axes[1,0])
plot_g(df,5,freq,axes[1,1])
plot_g(df,6,freq,axes[1,2])