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):
        radius = 0.3
        plt.plot(x+radius*c, y+radius*s,'k',alpha=0.35)  # draw unit circle
        plt.plot([x,x+radius*np.real(Z)],[y,y+radius*np.imag(Z)],'k',alpha=0.35) # draw radius
        plt.plot(x+radius*np.real(Z),y+radius*np.imag(Z),'o',markersize=markersize,color=colors[(j*k)%len(kvals)]) # mark 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)