# 538 Day -4: DFT and trigonometric interpolation (review)¶

## Visualization of the matrix of the discrete Fourier transform¶

In [1]:
from numpy import *
from matplotlib import rcdefaults
#rcdefaults()  # restore default matplotlib rc parameters
%config InlineBackend.figure_format='retina'
#import seaborn as sns  # wrapper for matplotlib that provides prettier styles and more
import matplotlib.pyplot as plt  # use matplotlib functionality directly
%matplotlib inline
#sns.set()

In [13]:
import numpy as np
from matplotlib import cm
from matplotlib.colors import LinearSegmentedColormap

def fft_matrix_viz(n):
L = 1.
vsep = -1.
markersize = 75./float(n)
i = complex(0.,1.)
t = linspace(0,L,501,endpoint=True)
kvals = range(0,n)#-n//2,n)
colormap = cm.get_cmap('hsv') # a cyclic colormap
nc = len(kvals)
colors = colormap( np.linspace(0,1,nc,endpoint=False) )  # get nc colors from the colormap
# pastelize colors
p = 0.5
colors = (1-p)*colors + p*ones_like(colors)
# darken colors
d = 0.9
colors *= [d,d,d,1]
plt.figure(figsize=(12, 12))

theta = np.linspace(0,2*np.pi,50)
c = np.cos(theta)
s = np.sin(theta)
def plotZ(x,y,Z):

plt.subplot(1,1,1,aspect=1,frameon=False)
for k in kvals:
zd = exp(-2*pi*i*k*arange(n)/float(n))
#zc = exp(-2*pi*i*k*t)
for j,Z in enumerate(zd): plotZ(j,vsep*k,Z)
plt.text(-0.5,vsep*k,str(k),va='center')

for j in range(n):
plt.text(j,vsep*(min(kvals)-0.5),str(j),ha='center')
plt.title('$F_{'+str(n)+'}$',fontsize=15)
plt.xlim(-.5,n+.5)
plt.ylim(vsep*(max(kvals)+1),vsep*(min(kvals)-1))
plt.xticks([])#kvals)
plt.yticks([])

plt.savefig('dft_visualization_'+'n'+str(n).zfill(4)+'.svg',bbox_inches='tight')

fft_matrix_viz(4)

In [14]:
fft_matrix_viz(8)


## Small example of DFT and IDFT¶

In [4]:
from scipy.fftpack import fft, ifft
x = [1,2,3,5]
y = fft(x)
y

Out[4]:
array([11.+0.j, -2.+3.j, -3.+0.j, -2.-3.j])
In [5]:
ifft(y)

Out[5]:
array([1.+0.j, 2.+0.j, 3.+0.j, 5.+0.j])
In [6]:
## the matrix?
fft(np.eye(4))

Out[6]:
array([[ 1.+0.j,  1.+0.j,  1.+0.j,  1.-0.j],
[ 1.+0.j,  0.-1.j, -1.+0.j,  0.+1.j],
[ 1.+0.j, -1.+0.j,  1.+0.j, -1.-0.j],
[ 1.+0.j,  0.+1.j, -1.+0.j,  0.-1.j]])

## Another visualization of the DFT matrix¶

In [16]:
n=16
def fft_matrix_viz2(n):
L = 1.
vsep = -4.
markersize = 150./float(n)
i = complex(0.,1.)
t = linspace(0,L,501,endpoint=True)
kvals = range(n)#-n//2,n)

plt.figure(figsize=(12, 12))

recolor,imcolor = '#4444ff','#ff4444'
plt.subplot(1,1,1)
for k in kvals:
zd = exp(-2*pi*i*k*arange(n)/float(n))
zc = exp(-2*pi*i*k*t)
plt.plot([0,n],[vsep*j,vsep*j],'#dddddd')
plt.plot(t*n,vsep*k+real(zc),recolor,alpha=0.25)
plt.plot(t*n,vsep*k+imag(zc),imcolor,alpha=0.25)
plt.plot(arange(n),vsep*k+real(zd),'.',color=recolor,markersize=markersize)
plt.plot(arange(n),vsep*k+imag(zd),'.',color=imcolor,markersize=markersize)
plt.text(-0.75,vsep*k,str(k),va='center')

plt.title('$F_{'+str(n)+'}$ : real part blue, imag part red')
plt.xlim(-.5,n+.5)
plt.ylim(vsep*(max(kvals)+1),vsep*(min(kvals)-1))
plt.xticks(range(n))
plt.yticks([])

plt.savefig('dft_visualization2_'+'n'+str(n).zfill(4)+'.png')

fft_matrix_viz2(4)

In [17]:
fft_matrix_viz2(16)