Note: Please read my previous article about the Discrete Fourier Transform first. It will help you get a better context of what's going on.

In the previous article, we implemented the Discrete Fourier Transform (DFT) in Python.

The DFT algorithm gave us a tool to find out the hidden patterns in a noisy signal. It does that by linearly transforming the vector of time values into a vector of frequency values. This exposes the amplitudes, frequencies and phases of the sinusoidal waves that make up the original signal.

In this article, let's look at the inverse process: transforming a vector of frequency values into a vector of time values.

Mathematically, the Inverse Discrete Fourier Transform (iDFT) is given by:

Here,

N is the number of samples.
n is the current sample.
k is the current frequency.
X[k] is the DFT at n.
x[n] is the iDFT at n.

This inverse process is possible because the discrete Fourier transform matrix is square and invertible (recall the matrix of exponential values from the previous article). Ideally, we should be able to get back our original noisy signal.

Let's start coding!

Python Code

The DFT function returned a vector of complex numbers that contained the amplitudes and phases at each frequency. We had called that vector X_k.

Now, we will use X_k to get back our original signal.

def iDFT(X_k):
    N = X_k.size
    n = np.arange(N)
    k = n.reshape((N,1))

    e = np.exp(2j * np.pi * k * n / N)
    x = np.zeros_like(X_k)

    for row in range(N):
        for col in range(N):
            x[row] += e[row, col] * X_k[col]

    x /= N

    return x.real

Key points to note here:

When we were declaring X_k in the DFT function, we had explicitly defined the datatype.

X_k = np.zeros_like(k, dtype=np.complex128)

But here, while declaring x, we don't have to mention the datatype, even though the actual mathematical operation involves complex numbers. Why?

That's because of the way the function zeros_like works. It not only copies the shape of the input argument, but also its datatype. In the case of X_k, k was a real vector. Since X_k would be involved with complex mathematical operations, we had to explicitly define its datatype to be complex.

In this case, X_k is already complex. Passing it as an argument to zeros_like makes x a complex vector as well.

While plotting the signal, we are interested only on the real part of the complex values. That is why x.real is returned, instead of just x.

This is the amplitude spectrum:

Let's use the iDFT function to reconstruct the signal, and compare it with the original signal.

inv_x = iDFT(X_k)

plt.figure(figsize = (14, 5))
plt.subplot(121)
plt.plot(t, x, 'b')
plt.xlabel('t')
plt.ylabel('x')
plt.title('Original Signal')
plt.grid(True)

plt.subplot(122)
plt.plot(t, inv_x, 'r')
plt.xlabel('t')
plt.ylabel('x')
plt.title('Reconstructed Signal')
plt.tight_layout()
plt.grid(True)

That's a really good reconstruction!

Of course, we had a clean signal to begin with. That has made the reconstruction process easier.

But this process is efficient with real-world signals as well. I hope it's clear how we can switch between the time and frequency domains using just the DFT matrix.

Vectorization

As I had said before, for loops are slow. So let's vectorize the iDFT function.

def viDFT(X_k):
    N = X_k.size
    n = np.arange(N)
    k = n.reshape((N,1))

    e = np.exp(2j * np.pi * k * n / N)
    x = np.dot(e, X_k) / N

    return x.real

Let's compare the time taken by the 2 functions.

Just like before, the vectorized function is faster by a factor of 10^4.

Continuing from the previous article, we have now implemented the Inverse Discrete Fourier Transform in Python.

In the next article, let's discuss an algorithm that speeds up the DFT algorithm by a large factor.

Hardik Medhi
Stay Curious

For more captivating science stories, follow me on Medium!

Implementing the Inverse Discrete Fourier Transform in Python

Let's implement the Inverse Discrete Fourier Transform in Python!

The all-in-one writing platform.

Write, publish everywhere, see what works, and become a better writer - all in one place.