Fourier Analysis in Signal Processing
In 1822, French mathematician and engineer Joseph Fourier, as part of his work on the study on heat propagation, showed that any periodic signal could be written as an infinite sum of trigonometric functions (cosine and sine functions). Fourier showed that any function, \(\ell(t)\) defined in the interval \(t \in (0,\pi)\), could be expressed as an infinite linear combination of harmonically related sinusoids, \[\ell(t) = a_1 \sin (t) + a_2 \sin (2t) + a_3 \sin (3t) + ...\] and that the value of the coefficients \(a_n\) could be computed as the area of the curve \(\ell(t) \sin (nt)\). Precisely, \[a_n = \frac{2}{\pi} \int_0^\pi \ell(t) \sin (nt) dt\]
However, the sum is only guaranteed to converge to the function \(\ell(t)\) within the interval \(t \in (0,\pi)\). One of Fourier’s original examples of sine series is the expansion of the ramp signal \(\ell(t)=t/2\). This series was first introduced by Euler. Fourier showed that his theory explained why a ramp could be written as the following infinite sum: \[\frac{1}{2} t = \sin (t) - \frac{1}{2} \sin (2t) + \frac{1}{3} \sin (3t) - \frac{1}{4} \sin (4t) + ...\]
The result of this series approximates the ramp with increasing accuracy as we add more terms. The plots in Figure 1 show each of the weighted sine functions (on top) and the resulting partial sum (bottom graphs). We can see how adding higher frequency sines adds more details to the resulting function making it closer to the ramp.
It is useful to think of the Fourier series of a signal as a change of representation as shown in Figure 2. Instead of representing the signal by the sequence of values specified by the original function \(\ell(t)\), the same function can be represented by the infinite sequence of coefficients \(a_n\). Fourier series can also be written as sums of different sets of harmonic functions.
The fields of signal and image processing have introduced different types of Fourier series. In the next sections we will study how these series are applied to describe discrete images using discrete sine and cosine functions and then we will focus on using complex exponentials.
Types of Fourier Analysis
There are two main types of Fourier analysis:
- Fourier Series: Used for signals that are periodic, which can be expressed as a discrete sum of trigonometric or exponential terms with specific frequencies.
- Fourier Transform: Used with continuous signals that are aperiodic, representing them as a continuous integral of trigonometric or exponential terms over a continuum of frequencies. The Fourier transform of aperiodic signals is simply called the Fourier Transform.
The continuous time sine wave is \[s\left(t\right) = A \sin\left(w ~t - \theta \right)\] where \(A\) is the amplitude, \(w\) is the frequency, and \(\theta\) is the phase. In discrete time, the discrete time sine wave is as follows \[s\left[n\right] = A \sin\left(w ~n - \theta \right)\] Note that the discrete sine wave will not be periodic for any arbitrary value of \(w\).
A discrete signal \(\ell\left[n\right]\) is periodic, if there exists \(T \in \mathbb{N}\) such that \(\ell\left[n\right] = \ell\left[n+mT\right]\) for all \(m \in \mathbb{Z}\). For the discrete sine (and cosine) wave to be periodic the frequency has to be \(w = 2 \pi K / N\) for \(K,N \in \mathbb{N}\). If \(K/N\) is an irreducible fraction, then the period of the wave will be \(T = N\) samples. The same applies for the cosine: \[c_k\left[n\right] = \cos\left(\frac{2 \pi}{N} \,k\,n \right)\]
This particular notation makes sense when considering the set of periodic signals with period \(N\), or the set of signals with finite support signals of length \(N\) with \(n \in \left[0, N-1\right]\). In such a case, \(k \in \left[1, N/2\right]\) denotes the frequency (i.e., the number of wave cycles that will occur within the region of support). Note that if \(k=0\) then \(s\left[n\right]\) = 0 and \(c\left[n\right]=1\) for all \(n\). One can also verify that \(c_{N-k} = c_k\), and \(s_{N-k} = -s_k\). Therefore, for frequencies \(k>N/2\) we find the same set of waves as the ones in the interval \(s \in \left[1, N/2\right]\).
Figure 3: Sine and cosine waves with \(A=1\) and \(N=20\). Each row corresponds to \(k=1\), \(k=2\) and \(k=3\). Note that for \(k=3\) the waves oscillates three times in the interval \(\left[0,N-1\right]\), but the samples in each oscillation are not identical, and it is only truly periodic once every \(N\) samples.
The same analysis can be extended to two dimensions (2D). In 2D, the discrete sine and cosine waves are as follows: \[s_{u,v}\left[n,m\right] = A \sin \left(2 \pi \left( \frac{u\,n}{N} + \frac{v\,m}{M} \right) \right)\] \[c_{u,v}\left[n,m\right] = A \cos \left(2 \pi \left( \frac{u\,n}{N} + \frac{v\,m}{M} \right) \right)\] where \(A\) is the amplitude and \(u\) and \(v\) are the two spatial frequencies and define how fast or slow the waves change along the spatial dimensions \(n\) and \(m\).
Figure 4: 2D sine waves with \(N=M=20\).
Euler’s formula is a fundamental concept in Fourier analysis: \[\exp \left(j a\right) = \cos (a) + j \sin (a) \tag{16.1}\]
Figure 5 shows the one dimensional (1D) discrete complex exponential function (for \(v=0\)). As the values are complex, the plot shows in the \(x\)-axis the real component and in the \(y\)-axis the imaginary component.
Figure 5: Complex exponential wave with (a) \(N=40\), \(k=1\), \(A=1\); and (b) \(N=40\), \(k=3\), \(A=1\). The red and green curves show the real and imaginary waves. The black line is the complex exponential.
In 2D, the complex exponential wave is \[e_{u,v}\left[n,m\right] = \exp \left(2 \pi j \left( \frac{u\, n}{N} + \frac{v\,m}{M} \right) \right)\]where \(u\) and \(v\) are the two spatial frequencies.
Note that complex exponentials in 2D are separable. A remarkable property is that the complex exponentials form an orthogonal basis for discrete signals and images of finite length. In this chapter we will focus on the discrete Fourier transform as it provides important tools to understand the behavior of signals and systems (e.g., sampling and convolutions).
Discrete Fourier Transform (DFT)
The Discrete Fourier Transform (DFT) is a specific type of Fourier analysis that is invaluable in understanding signals and systems. The general equation for DFT is:\tag{16.2}\]
We will call \(\mathscr{L}\left[u,v \right]\) the Fourier transform of \(\ell\left[m,n \right]\). As we can see from the inverse transform equation, we rewrite the image, instead of as a sum of offset pixel values, as a sum of complex exponentials, each at a different frequency, called a spatial frequency for images because they describe how quickly things vary across space.
As \(\mathscr{L}\left[u,v \right]\) is obtained as a sum of complex exponential with a common period of \(N,M\) samples, the function \(\mathscr{L}\left[u,v \right]\) is also periodic: \(\mathscr{L}\left[u+aN,v+bM \right] = \mathscr{L}\left[u,v \right]\) for any \(a,b \in \mathbb{Z}\). Also the result of the inverse DFT is a periodic image.
Using the fact that \(e_{N-u, M-v} = e_{-u,-v}\), another equivalent way to write for the Fourier transform is to sum over the frequency interval \(\left[-N/2, N/2\right]\) and \(\left[-M/2, M/2\right]\). This formulation allows us to arrange the coefficients in the complex plane so that the zero frequency, or DC, coefficient is at the center.
Slow, large variations correspond to complex exponentials of frequencies near the origin. If the amplitudes of the complex conjugate exponentials are the same, then their sum will represent a cosine wave; if their amplitudes are opposite, it will be a sine wave. Frequencies further away from the origin represent faster variation with movement across space.
The DFT became very popular thanks to the Fast Fourier Transform (FFT) algorithm. As the DFT is a linear transform we can also write the DFT in matrix form, with one basis per row. Each entry in the matrix is \(\mathbf{F}_{u,n} = \exp{ \left(-2\pi j \frac{u\, n}{N} \right)}\), with \(u\) indexing rows and \(n\) indexing columns. Note that \(\mathbf{F}\) is a symmetric matrix.
Working in 1D, as we did before, allows us to visualize the transformation matrix. Figure 6 shows a color visualization of the complex-value matrix for the 1D DFT, which when used as a multiplicand yields the Fourier transform of 1D vectors.
Figure 6: Visualization of the discrete Fourier transform as a matrix. The signal to be transformed forms the entries of the column vector at right. The complex values of the Fourier transform matrix are indicated by the color, with the key in the bottom left.
When computing the DFT of a real image, we will not be able to write the analytic form of the result, but there are a number of properties that will help us to interpret the result. Figure 7 shows the Fourier transform of a \(64 \times 64\) resolution image of a cube.
As the DFT results in a complex representation, there are two possible ways of writing the result. Using the real and imaginary components: \[\mathscr{L}\left[u,v \right] = Re \left\{\mathscr{L}\left[u,v \right] \right\} + j \, Imag \left\{\mathscr{L}\left[u,v \right] \right\}\] where \(Re\) and \(Imag\) denote the real and imaginary part of each Fourier coefficient. Or using a polar decomposition: \[\mathscr{L}\left[u,v \right] = A \left[u,v \right] \, \exp{\left( j \, \theta\left[u,v \right] \right)}\] where \(A \left[u,v \right] \in \mathbb{R}^+\) is the amplitude and \(\theta \left[u,v \right] \in \left[-\pi, \pi \right]\) is the phase.
Upon first learning about Fourier transforms, it may be a surprise for readers to learn that one can synthesize any image as a sum of complex exponentials (i.e., sines and cosines). To help gain insight into how that works, it is informative to show examples of partial sums of complex exponentials. Figure 8 shows partial sums of the Fourier components of an image. In each partial sum of \(N\) components, we use the largest N components of the Fourier transform.
Using the fact that the Fourier basis functions are orthonormal, it is straightforward to show that this is the best least-squares reconstruction possible from each given number of Fourier basis components. This first image shows what is reconstructed from the largest Fourier component which turns out to be \(\mathscr{L}\left[0,0 \right]\). This component encodes the DC value of the image, therefore the resulting image is just a constant. The next two components correspond to two complex conjugates of a very slow varying wave. And so on. As more components get added, the figure slowly emerges.
Figure 8: Reconstructing an image from the \(N\) Fourier coefficients of the largest amplitude.
It’s useful to become adept at computing and manipulating simple Fourier transforms. \exp{ \left( -2\pi j \left( \frac{u\, n}{N} + \frac{v\, m}{M} \right) \right)} = 1\] where the Fourier transform of the delta signal is 1.
Figure 9: Some 2D Fourier transform pairs. Images are \(64 \times 64\) pixels. The waves are cosine with frequencies \((1,2)\), \((5,0)\), \((10,7)\), \((11,-15)\).
Figure 10 shows the 2D Fourier transforms of some periodic signals. The depicted signals all happen to be symmetric about the spatial origin. From the Fourier transform equation, one can show that real and even input signals transform to real and even outputs. So for the examples of Figure 10, we only show the magnitude of the Fourier transform, which in this case is the absolute value of the real component of the transform, and the imaginary component happens to be zero for the signals we’ll examine. Also, all these images but the last one are separable (they can be written as the product of two 1D signals).
Note the trends visible in the collection of transform pairs: As the support of the image in one domain gets larger, the magnitude in the other domain becomes more localized. A line transforms to a line oriented perpendicularly to the first. The box function is a very useful function that we will use several times in this book. It is good to be familiar with its Fourier transform and how to compute it.
The box function takes values of 1 inside the interval \(\left[ -L,L \right]\) and it is 0 outside. It is useful to think of the box function as a finite length signal of length \(N\) and to visualize its periodic extension outside of that interval. The following plot shows the box function for \(L=5\) and \(N=32\). We will compute here the DFT of the finite length box function, with a length \(N\).
We can use the equation of the sum of a geometric series: \[\sum_{n=-L}^{L} a^n = a^{-L} \sum_{n=0}^{2L} a^n = a^{-L} \frac{1-a^{2L+1}}{1-a} = \frac{a^{-(2L+1)/2}-a^{(2L+1)/2}}{a^{-1/2}-a^{1/2}}\]where \(a\) is a constant.
Where \(a\) is a constant. We will denote the DFT of the box function, \(\text{box}_{L} \left[n \right]\), capitalizing the first letter, \(\text{Box}_{L} \left[u \right]\). This function has its maximum value at \(u=0\). The DFT, \(\text{Box}_{L} \left[u \right]\), is a symmetric real function. The following plot (Figure 11) shows the DFT of the box with \(L=5\), and \(N=32\).
Now that we know how to compute the DFT of the 1D box, we can easily extend it to the 2D case. A 2D box is a separable function and can be written as the product of two box functions, \(\text{box}_{L_n, L_m} \left[n,m\right] = \text{box}_{L_n} \left[n\right] \text{box}_{L_m}\left[m\right]\). It is important to be familiar with the properties for the DFT.
- Linearity: The DFT is linear, meaning that the transform of a linear combination of signals is the same as the linear combination of their transforms: \alpha \mathscr{L}_1 \left[u,v \right] + \beta \mathscr{L}_2 \left[ u,v \right]\] where \(\alpha\) and \(\beta\) are complex numbers. This property can be easily proven from the definition of the DFT.
- Separability: An image is separable if it can be written as the product of two 1D signals, \(\ell\left[n,m \right] = \ell_1\left[n \right] \ell_2\left[m \right]\). Although almost all images are not separable, some can be approximated by a separable image. We can use the SVD decomposition to find a separable approximation to this image.
- Parseval's Theorem: As the DFT is a change of basis, the dot product between two signals and the norm of a vector is preserved (up to a constant factor) after the basis change. \end{split}\] In these sums, the finite signal \(\ell_1 \left[n, m \right]\) of size \(N \times M\) is extended periodically.
Fourier Analysis Networks (FANs)
For most AI models today, their foundation is often built upon multi-layer perceptrons (MLPs), which is an artificial (feedforward) neural network with multiple layers. These types of models often suffice for most types of supervised data and can achieve relatively high accuracy after setting the optimal parameters and hyperparameters. However, these models have a more difficult time predicting data that exhibits periodicity (i.e. the frequency of observations in data over time).
MLPs treat inputs as independent and lack mechanisms to capture temporal or sequential patterns. MLPs struggle to effectively learn and predict periodic data since they do not possess the ability to model frequency, amplitude, or phase shifts in periodic signals. Fourier analysis networks (FANs) aim to resolve this current gap. Built on the mathematical principles of Fourier analysis, these networks show immense promise in handling structured and periodic data, particularly in applications like time-series forecasting and signal processing.
Fourier analysis studies how general functions can be decomposed into trigonometric or exponential functions with defined frequencies. This decomposition is essential for understanding periodic and structured data, making Fourier analysis vital in scientific fields and engineering. For instance, periodic data such as audio signals, electromagnetic waves in communication systems, and repeating patterns in image processing (e.g., the compression of JPEG images) all rely on Fourier analysis in their applications.
Fourier transforms are typically described as the exponential decomposition of a function. Its mathematical expression is found below. For a given function f(t), the Fourier transform F(ω) is defined as:
Here, f(t) represents the input function (for example, a signal), and ω is the angular frequency. Additionally, F(ω) describes the signal in terms of its frequency components, showing which frequencies are present. From a signal processing perspective, given some signal, we can use the Fourier transform to deconstruct different parts of the signal into corresponding sine and cosine waves.
With this, these are some key properties that the Fourier Transform has:
- Frequency Decomposition: It separates a signal into its constituent frequencies, helping identify “dominant” signal components.
- Bidirectional Transformation: We can obtain an inverse Fourier transform that allows reconstruction of the original signal given its frequency representation.
In the context of time-series forecasting, one of the most important techniques in predictive analytics within machine learning, Fourier Transforms are particularly valuable because they reveal the periodic components in a dataset, (i.e. time-based trends), enable signal filtering by Isolating specific frequencies to remove noise and extract relevant pattern, and are able to utilize such periodic components to accurately predict trends over time.
Fourier analysis networks combine traditional neural layers with frequency-based representations, creating a robust hybrid model for structured data. At their core, they use sinusoidal functions to represent data in the form of frequencies. This integration is often achieved through Fourier feature mappings.
Fourier feature mapping is a technique that takes raw input data and transforms it into a higher-dimensional space using sine and cosine functions. This transformation allows the neural network to analyze the data in terms of its frequency components rather than just its raw values. Mathematically, according to Dong et al. (2024), the transformation can be expressed as:
where Bp̄ and Wp̄ are learnable parameters; Bp̄ usually denotes a parameter that controls the frequencies of the sine and cosine functions used in the Fourier feature mapping, while Wp̄ is a vector that contains values that weight the influence of each Fourier basis function in the model.
Once the input data has been transformed using Fourier feature mapping, these new features are fed into a neural network. From this, the same principles apply with how neural networks learn via supervised learning. The model can recognize complex patterns more easily because it is working with features that highlight periodic behavior in time-series data (FANs decompose input data into multiple sinusoidal components). By using Fourier features, neural networks can converge faster during training and thus learn high-frequency signals more efficiently. More importantly, they are able to efficiently handle datasets with overlapping periodicities. Finally, by incorporating Fourier basis functions, the network generalizes better to unseen data.
Traditional neural networks require more layers and parameters to approximate periodic patterns. Fourier networks achieve the same with fewer resources, as they explicitly model these patterns with sinusoidal functions. In effect, FANs help the neural network learn periodic or repetitive patterns more accurately and efficiently.
Right off the bat, we can examine the equations and see that FANs are superior from an efficiency standpoint. Looking at the number of parameters in each layer, note that compared to the MLP layer, the FAN layer has an additional factor of 1-(d_p / d_output) which is less than 1. Consequently, the number of parameters in the FAN layer is less than that of the MLP layer. Similarly, looking at the number of floating-point operations (FLOPs) of both layers, the same can be said, with the FAN layer having an additional factor of 1-(d_p / d_output) which is less than 1.
From a performance standpoint, we can see that FANs do a phenomenal job in modeling periodicity compared to other models like MLPs, Kolmogorov-Arnold networks (KANs) and Transformers. From Dong et al., the graph above shows that FANs do “exceptionally well on test data both within and outside the domain of the training data, indicating that it is genuinely modeling periodicity rather than merely memorizing the training data.”
FANs have proven especially effective in applications such as signal processing, stock market analysis, and seismology, where understanding frequency-based patterns is critical. In signal processing, FANs are used to filter noise, enhance audio quality, and compress data for efficient transmission. By analyzing signals and their frequencies, FANs can isolate relevant features that enable clearer communication or improved audio quality.
In stock market analysis, FANs help detect cyclical trends and recurring patterns within financial time series data to more accurately predict market movements and identify potential opportunities based on frequency-driven price fluctuations. Finally, in seismology, FANs play a pivotal role in processing seismic data, separating low-frequency noise from high-frequency earthquake signals, which aids in real-time earthquake detection and prediction.