Ch 11: The Discrete Time Fourier Transform, the FFT, and the Convolution Theorem

This chapter directly expands on the previous by talking about how the Fourier Transform works and what it is used for, as well as the Convolution Theorem and its implications. This is an important chapter as the the Fourier Transform is the backbone of many analyses!

11.1 Making Waves

The general equation of a sine wave is:

Asin(2πf t + θ)

• A is the amplitude
  • Power is amplitude squared, and is a term you may see used interchanged 
• f is the frequency
  • The number of cycles per seconds, expressed as Hz
• t is the time
  • The time you are calculating the wave in seconds. This is the dependent variable of the equation
• θ is the phase
  
  • Measured in radians or in degrees (be careful here), essentially is the offset of the whole wave in regards to time

Use online graphing calculates and play with the sine equation until you feel familiar with how changing these properties changes the resultant wave!

On a 2D representation, we see sine waves cycling up and down. However, as discussed in the future, sine waves can be better described as a 3D spiral going through space (phasors), and the 2D plot is just a projection of this onto a plane.

You can take several sine waves, and add them together to get a more complicated signal.

11.2 Finding Waves in EEG Data with the Fourier Transform

With analysis of EEG time-series data, we want to know the frequency makeup of the signal. That is where the Fourier Transform comes in, as it gives us that information. 

While realistically you will be using pre-made functions to do the Fourier Transform (or more practically, the Fast Fourier Transform, more on this later), it is still important to understand where this comes from.

11.3 The Discrete Time Fourier Transform

The Fourier Transform inconverts time-series data into an output showing the frequency, power, and phase. In its original form is straight forward, Use a sine wave as a kernel and take the dot product with the time series data. Then repeat with another sine wave at another frequency. Then repeat again and again until you map out the frequency spectrum.

The number of since waves and the frequency of each is determined by the number of data points in the time-series data. In addition, instead of using "sin" directly as a function, we use Euler's Formula to use the form e^-1ix of sine waves instead (more on this in Chapter 13).

The frequency of each sine wave iteration is equivalent to 2 * π * (Loop_Index). This does mean that the very first sine wave iteration we take has a frequency of zero. A sine wave of 0 frequency is a straight line, and the dot product using this gives us what is called the DC Component of the signal (DC being Direct Current). The DC Component is the mean offset of the entire signal.

The number of times / iterations we do is dependent on Nyquist's Theorem. It states that to sample any sine wave, you must sample at least 2 times per cycle. Ergo, the number of frequencies we can sample from a signal is one half of the total number of points in the time-series data set of the signal, plus 1 (the +1 being from the DC Component where frequency is 0). 

This can be written as the following formula:

NOTE: This equation was changed from the textbook, where it denoted as k = 1. As k is the loop index, the Textbook which is written for Matlab used k = 1 since Matlab loop indexing starts at 1. However, generally indexing in other actually sane languages starts at 0, so I changed this to k = 0 to be more in line in generic use

An understanding on the Discrete Fourier Transform (the original form) is important. If the above explanation is confusing, I highly suggest checking out this video for a more visual overview

11.4 Visualizing the Results of a Fourier Transform

The Fourier Transform output is once again, a 3D structure with its dimensions being the frequency, power, and phase information of the ingested time-series signal. Generally, phase information is  ignored in visualizations, thus data is often expressed as 2D plots of the power levels of various frequencies.

(Input signal on top, the Fourier Transform plot of frequency vs power below)

Technically, since the output of each frequency is discrete (IE we don't have a continuous view of all possible frequencies, we examined specific frequencies in the processes of the Fourier Transform), bar graphs are to be used to represent this data. However, sometimes there are so many frequency bins to show that the information is extremely dense, so it may be more practical to use a line graph instead.

11.5 Complex Results and Negative Frequencies

The Fourier Transform output may contain negative frequencies in its output. These are sine waves that travel in the reverse order around the complex plane (more on this later). These negative frequencies are important for the Hilbert transform (also discussed later).

In addition, signal that has only real numbers as the input, such as with EEG signal, will product negative frequencies that mirror the positive frequencies. Thus we can technically represent everything by ignoring the negative frequencies and doubling the amplitude of the positive frequencies in our visualizations. However, the negative frequencies are still important for taking the inverse transform.

11.6 Inverse Fourier Transform

The Inverse Fourier Transform converts the 3D result of the Fourier Transform back into the original time-series data, with no information lost. 

Conceptually it is straight forward. The Fourier Transform operates on the principal that a (constant) signal can be represented by a summation of various sine waves, and so the Fourier Transform reveals what the since waves are. Now if you take those outputted sine waves, at their given frequencies, power, and phase, and sum them up, you end up with the original signal. This is how the Inverse Fourier Transform works.

11.7 The Fast Fourier Transform

As hinted heavily earlier, you will never actually use the Discrete Fourier Transform in your calculations. The reason for this is that it is computationally slow. Realistically you will use the Fast Fourier Transform (FFT) in your work, which is magnitudes faster, especially as the size of the input signal grows.

How the FFT works is less important to know, but essentially it cuts out a lot of the math of the repeated do products required as they are technically redundant. 

For further context to programmers, in big O notation, the Discrete Fourier Transform is O(N²), while the Fast Fourier Transform is N(log(N)).

11.8 Stationarity and the Fourier Transform

As hinted a few times, the Fourier Transform assumes a constant signal. A constant signal means that the component sine waves making a signal never change, and thus the signal repeats forever (this may also be referred to as a 'well behaved' or 'stationary' signal). This is not the case with EEG, as neural states are constantly shifting, so does the signal. This actually can cause problems using the Fourier Transform during analysis.

These violations can decrease the peaks in Fourier Transform visualizations

(The 2 input time series both used sine waves of the same frequencies (that being 3, 5, 7, and 10 Hz) and amplitude, but one was non-stationary. As visible in the results, the non-stationary FFT output shows a spread of calculated frequencies with low peaks at the actual frequencies. This is technically not correct, and is what occurs when the assumption of constant signal is violated).

This is why Fourier Transforms in signals such as EEG are done on very short duration windows (locally temporaly with windows of a few hundred ms), in analysis such as wavelet convolution, filter-Hilbert, and short-time FFT. 

There is another issue with Fourier Transform, the results do not show change in a signal over time. This is another reason why local temporal methods are used instead.

11.9 Extracting More or Fewer Frequencies than Data Points

As discussed earlier, typically the number of frequencies in the Fourier Transform of a time-series set is the number of points in that set, divided by two, plus one. 

You can technically add more frequencies to the analysis (keep in mind this increases the resolution, NOT the precision!) by padding the end of the input time series signal with zeros. You can decrease the resolution by removing points.

These methods can be used to make frequency-domain convolution (as discussed next) more convenient / faster to preform. 

11.10 The Convolution Theorem

Now lets bring this all together with what we learned about convolution in the last chapter!

The Convolution Theorem simply states that Convolution in the time domain = multiplication in the frequency domain. In other words, one can take the convolution the way we discussed before:

• Flip the kernel
• Slide the flipped kernel along the signal
• Compute the dot product at each step
• at each step, append the outputted point to the growing output

OR, by using the convolution theorem

• Compute the FFT of the kernel and the signal
• Multiply the two together point by point (frequency to frequency).
• Take the Inverse Fourier Transform

The second is computationally MUCH faster than the initial way we learned about convolutions!

The Convolution theory also hints something else: that convolution is in a sense a band-pass frequency domain filter. Since you can think of multiplying the two Fourier Transforms as scaling them with each other (IE, scaling the result of the FFT of the signal with the FFT of the kernel), by choosing a kernel of a specific frequency (albeit using gaussians), we can essentially band-pass filter for that frequency range in the signal (since other frequencies of such a kernel would be 0, and multiplying by 0 is 0). By making the kernel Gaussian wider or more narrow, we can control the width of the bandpass.

(In the given example, the input signal is a 20 Hz sine wave. A narrow kernel (15 Hz) dampens the signal, while a wide kernel (5 Hz) deletes it. Keep in mind the start and end of the convolution results are examples of edge artifact). 

This can of course also be applied to actual EEG data as well:

(As you can see in this example, the kernel acts as a low pass filter).

Gaussians may not make the best kernels for this purpose in all cases. Sometimes other kernels can be used, and as such, this method is the basis of Wavelet Convolution.

11.11 Tips for Performing FFT-Based Convolution in Matlab

This section is specifically about the Matlab Specific funcitons for the forward and reverse Fourier Transforms, and ensuring the correct number of points are outputted for various uses.