Convolutional Theorem

Important note: this particular section will be expanded upon after the Fourier transform and Fast Fourier Transform (FFT) chapters have been revised.

Now, let me tell you about a bit of computational magic:

Convolutions can be performed with Fourier Transforms!

This is crazy, but it is also incredibly hard to explain, so let me do my best. As described in the chapter on Fourier Transforms, Fourier Transforms allow programmers to move from real space to frequency space. When we transform a wave into frequency space, we can see a single peak in frequency space related to the frequency of that wave. No matter what function we send into a Fourier Transform, the frequency-space image can be interpreted as a series of different waves with a specified frequency. Each of these waves is parameterized by another term, where is the element's value in the frequency domain, is its value in the time domain, and is the overall length of the signal. In this way, each wave can be seen as a complex exponential.

So here's the idea: if we take two functions and and move them to frequency space to be and , we can then multiply those two functions and transform them back into to blend the signals together. In this way, we will have a third function that relates the frequency-space images of the two input functions. This is known as the convolution theorem which looks something like this:

Where denotes the Fourier Transform.

At first, this might not seem particularly intuitive, but remember that frequency space is essentially composed of a set of exponentials. As mentioned in the section about Multiplication as a Convolution, multiplication in base 10 space is also a convolution. The convolutional theorem extends this concept into multiplication with any set of exponentials, not just base 10. Obviously, this description is still lacking a bit of explanation, but I promise we will add more when revising the Fourier transform sections!

By using a Fast Fourier Transform (FFT) in code, this can take a standard convolution on two arrays of length , which is an process, to . This means that the convolution theorem is fundamental to creating fast convolutional methods for certain large inputs.

function convolve_fft(signal1::Array{T}, signal2::Array{T}) where {T <: Number}
    return ifft(fft(signal1).*fft(signal2))
end

This method also has the added advantage that it will always output an array of the size of your signal; however, if your signals are not of equal size, we need to pad the smaller signal with zeros. Also note that the Fourier Transform is a periodic or cyclic operation, so there are no real edges in this method, instead the arrays "wrap around" to the other side, creating a cyclic convolution like we showed in the periodic boundary condition case for the one-dimensional convolution.

Example Code

using FFTW
using DelimitedFiles

# using the convolutional theorem
function convolve_fft(signal1::Array{T}, signal2::Array{T}) where {T <: Number}
    return ifft(fft(signal1).*fft(signal2))
end

function main()

    # Random distribution in x
    x = rand(100)

    # Gaussian signals
    y = [exp(-((i-50)/100)^2/.01) for i = 1:100]

    # Normalization is not strictly necessary, but good practice
    normalize!(x)
    normalize!(y)

    # cyclic convolution via the convolutional theorem
    fft_output = convolve_fft(x, y)

    # outputting convolutions to different files for plotting in external code
    writedlm("fft.dat", fft_output)

end

License

Code Examples

The code examples are licensed under the MIT license (found in LICENSE.md).

Text

The text of this chapter was written by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.

Pull Requests

After initial licensing (#560), the following pull requests have modified the text or graphics of this chapter:

  • none

results matching ""

    No results matching ""