More on the 1D DFT

More on the 1D DFT#

import numpy as np
import scipy.linalg
import matplotlib.pyplot as plt
def do_plots(f):
    g = np.fft.fft(f)
    
    plt.clf()
    fig = plt.figure(figsize=(10,3))

    plt.subplot(131)
    plt.plot(x, f)

    plt.subplot(132)
    plt.plot(x, np.real(g))
    plt.plot(x, np.imag(g))

    plt.subplot(133)
    h = np.fft.ifft(g)
    plt.plot(x, np.real(h))
    plt.plot(x, np.imag(h))

    plt.show()


# Question 1
# Look at sin(kx) and cos(kx)

n = 32
x = np.linspace(0,n-1,n)
dx = x[1]-x[0]

k = 2*np.pi * (2/n)
do_plots(np.cos(k*x))

do_plots(np.sin(k*x))


# when we add n to the frequency, we get the same answer
# the result is aliased back into our range
k = 2*np.pi * (2/n + n)
do_plots(np.cos(k*x))

# a non-integer frequency gives leakage into other bins
# the discontinuity at the boundaries leads to high freq components
k = 2*np.pi * 3.33/n
do_plots(np.cos(k*x))
<Figure size 640x480 with 0 Axes>
_images/9cd979b5596852aacfd36e4482ff3b3c2bc37b4b29e1cfc103c8e02dcd47aa03.png
<Figure size 640x480 with 0 Axes>
_images/bf299b853478bff93ea433718d6dee838913e9c525f9141fd75f70896aeafcbe.png
<Figure size 640x480 with 0 Axes>
_images/5ec675c2d532a98216a1be69a5d78338d59bc371cc126c02e81e6a92d50045cf.png
<Figure size 640x480 with 0 Axes>
_images/d6c65eb1462f76bb50e4330edd7974d735b26360ed075c0a3c82f4692f565012.png
# Gaussian
n = 128
x = np.linspace(-0.5,0.5,n)
dx = x[1]-x[0]

f = np.exp(-(x-0)**2/(0.02**2))
g = np.fft.fft(f)

fig = plt.figure(figsize=(10,3))

plt.subplot(131)
plt.plot(x, f)

plt.subplot(132)
gs = np.fft.fftshift(g)
plt.plot(x, np.real(gs))
plt.plot(x, np.imag(gs))
plt.plot(x, np.abs(gs))

plt.subplot(133)
# Check the inverse transform
h = np.fft.ifft(g)
plt.plot(x, np.real(h))
plt.plot(x, np.imag(h))
plt.show()

# Check Parseval's theorem
sumf = np.sum(np.abs(f)**2)
sumg = np.sum(np.abs(g)**2)/n
print('Parseval check:', sumf, sumg, sumf-sumg)

plt.clf()
# This shows that the real part is symmetric about k=0
# but the imaginary part is anti-symmetric; therefore F(-k) = F^*(k)
fig = plt.figure(figsize=(10,3))
plt.subplot(121)
k = np.fft.fftfreq(n)
plt.plot(k[k>0], np.real(g[k>0]))
plt.plot(-k[k<0], np.real(g[k<0]))

plt.subplot(122)
plt.plot(k[k>0], np.imag(g[k>0]))
plt.plot(-k[k<0], np.imag(g[k<0]))
_images/bcd1fcf45bd44cd7610555d03c4191a5041eb614bece56c4577a3b3cae5cc2b8.png
Parseval check: 3.18341790878128 3.18341790878128 0.0
[<matplotlib.lines.Line2D at 0x11cdbe780>]
<Figure size 640x480 with 0 Axes>
_images/5fdd120ddd10dfb2065d4577fb4e44a326559179454b14609bd5a2d7544067f7.png
# Question 2: manipulating f(x) by changing F(k)

n = 128
x = np.linspace(-0.5,0.5,n)
dx = x[1]-x[0]

f = np.exp(-(x-0)**2/(0.02**2)) + x
g = np.fft.fft(f)

fig = plt.figure(figsize=(10,4))

plt.subplot(131)
plt.plot(x, f)

plt.subplot(132)
# complex conjugate is equivalent to x->-x
h = np.fft.ifft(np.conjugate(g))
plt.plot(x, np.real(h))
plt.plot(x, np.imag(h))

plt.subplot(133)
# add a gradient in phase is equivalent to a translation in x
j = complex(0,1)
k = (2*np.pi/dx) * np.fft.fftfreq(n)
g = g * np.exp(-j * k * 0.2)

h = np.fft.ifft(g)
plt.plot(x, np.real(h))
plt.plot(x, np.imag(h))
plt.show()
_images/05166b3facda60fa149cb6561f56e95f2a5ce11bb032255359ba19b9ff580f3d.png
# Question 3: convolution
import scipy.signal

def convolution(f,g):
    ft = np.fft.fft(f)
    gt = np.fft.fft(g)
    return np.fft.ifft(ft*gt)

n = 1024
x = np.linspace(-0.5,0.5,n)
dx = x[1]-x[0]

f = np.exp(-(x)**2/(0.02**2))
g = np.zeros_like(x)
g[(x>-0.2)&(x<0.2)] = 1

plt.plot(x,f)
plt.plot(x,g)
h = convolution(g,f)
h = np.roll(h, n//2)  # shift the result to centre it
plt.plot(x,np.real(h)/np.max(np.real(h)))

# Compare against the scipy convolution function
h = scipy.signal.convolve(g,f, mode='same')
plt.plot(x,h/np.max(h),':')
[<matplotlib.lines.Line2D at 0x12d07fce0>]
_images/89ade397f47d28a3e525cae9392b412e93258994cd8cc02916eb18f6df837e10.png
# This wasn't one of the questions, but have a look at the 
# top hat <-> sinc function transform
n = 64
x = np.linspace(0,1,n)
dx = x[1]-x[0]

f = np.zeros_like(x)
f[(x>0.45)&(x<0.55)] = 1

g = np.fft.fft(f)

fig = plt.figure(figsize=(10,4))

plt.subplot(131)
plt.plot(x, f)

plt.subplot(132)
gs = np.fft.fftshift(g)
plt.plot(x, np.real(gs))
plt.plot(x, np.imag(gs))
plt.plot(x, np.abs(gs))

plt.subplot(133)

h = np.fft.ifft(g)
plt.plot(x, np.real(h))
plt.plot(x, np.imag(h))

plt.show()
_images/b027756d985df2f86e1312a82284e5fd9a4fa73a70dde3778fde773ace2ac2f1.png
# Question 4: red noise and random walk

n = 1024
x = np.linspace(0,1,n)
dx = x[1]-x[0]

f = np.random.randn(n)

g = np.fft.fft(f)

fig = plt.figure(figsize=(10,4))

plt.subplot(131)
plt.plot(x, f)

plt.subplot(132)
g2 = g.copy()
j = complex(0,1)
k = (2*np.pi/dx) * np.fft.fftfreq(n)
g2[1:] /= j*k[1:]

plt.plot(k[k>0], np.abs(g2[k>0])**2, '.')
plt.yscale('log')
plt.xscale('log')

plt.subplot(133)

h = np.fft.ifft(g2)
plt.plot(x, np.real(h))
#plt.plot(x, np.imag(h))

plt.show()

plt.clf()
plt.plot(np.real(h[:n//2])/dx, np.real(h[n//2:])/dx)
plt.show()
_images/544a6ebec111f76da17a6ac9f25ad132c50a05957219dfb6bb7a2bce40015f5e.png _images/2a2e3a0503700c03c6e39115d7a800a8531c013de034bdfd2e0ef4107673a8f9.png

In this question, we generate a sample of red noise which has a power spectrum \(1/k^2\) by taking the Fourier transform of white noise (flat power spectrum) and dividing the Fourier transorm by \(ik\). This is equivalent to integrating the white noise, since

\[g(x) = \int^x dx^\prime f(x^\prime) = \int^x dx^\prime \int dk\ F(k) e^{ikx^\prime} = \int dk\ F(k) \int^x dx^\prime e^{ikx^\prime} = \int dk\ {F(k)\over ik} e^{ikx}.\]

When we take the samples of red noise and plot them, we see a random walk (you can see that the distance travelled is \(\sim \sqrt{N}\) as expected). Individual steps in the random are uncorrelated (white noise) but because successive steps add up over time (integrate) we get a red noise spectrum in the end.

This is an interesting way to generate a random walk.