1
$\begingroup$

The (discrete and continuous) Fourier transform (FT) is used in signal processing in order to convert a signal (or function) in a certain domain (e.g. the time domain) to another domain (e.g., frequency domain). There are several resources on the web that attempt to explain the FT at different levels of complexity. See e.g. this answer or this and this Youtube videos.

What are examples of (real-world) applications of the Fourier transform to AI? I am looking for answers that explain the reason behind the use of the FT in the given application. I suppose that there are several applications of the FT to e.g. ML (data analysis) and robotics. I am looking for specific examples.

$\endgroup$
0
1
$\begingroup$

To be precise, a discrete Fourier transform can be used to transform a finite set of samples between frequency and time domains. A continuous Fourier transform can be applied in calculus to an expression or a set of equations (through the appropriate techniques) or used to develop algorithms, but digital systems are not continuous, so there is no way to directly integrate in a digital computer except symbolically.

When the features contained in time series or pixels are more easily extracted from spectral information or frequency domain complex numbers than from the time series, an FFT can produce the data in a form that supports easy extraction. For streams containing indefinitely long time series, a windowing scheme may be used. The common cases are for sound recognition and music recognition. FFTs are also used in the finite math involved in cryptography and especially cryptanalysis (code breaking). In robotics, FFTs would most likely be used in vibration analysis to reduce wear and dampen oscillation.

$\endgroup$
0
1
$\begingroup$

The filtering (or convolution) process in Convolutional Neural Networks can be implemented using Fourier Transforms. Convolutions in image (or spatial) space are equivalent to multiplications in frequency space, and multiplications can be performed much more efficiently than convolutions.

The algorithm for using Fourier Transforms to calculate a convolution between an image and a filter kernel is as follows:

Assuming a 100x100 input image, and a 3x3 filter kernel (such as a Sobel Edge-Detection filter).

  1. Calculate the 2D Fourier Transform (FT) of the image (C library, Python library)
  2. Pad the filter kernel so that it is the same size as the image, and that the filter kernel is centred at image coordinate (0, 0). This means that some parts of the kernel will be placed in the other corners of the padded filter image. For example, consider a 3x3 kernel where the filter coefficients are [[a, b, c], [d, e, f], [g, h, i]], in this case the coefficients map to pixel positions on the padded kernel as follows:

    • a -> (99, 99) //bottom right
    • b -> (0, 99) //bottom left
    • c -> (1, 99)
    • d -> (99, 0) //top right
    • e -> (0, 0) //top left
    • f -> (1, 0)
    • g -> (99, 1)
    • h -> (0, 1)
    • i -> (1, 1)

    Set all the other padded filter kernel pixels to zero

  3. Calculate the 2D Fourier Transform of the padded filter kernel.

  4. Perform an element-wise multiplication of the image FT and the padded filter kernel FT. Note that this is a complex multiplication as the FT consists of complex numbers. The result of this multiplication is therefore also an array of complex numbers.

  5. Calculate the Inverse Fourier Transform of the result from step 4. This will return a real valued image which is the original image convolved with the filter kernel.

The advantage for performing the kernel convolutions in this way is that it is much faster than performing an element-wise convolution directly. This speeds up the training process for neural networks with Convolutional layers.

$\endgroup$
1
  • 1
    $\begingroup$ For a general overview of digital signal processing (including image processing), I recommend dspguide.com/pdfbook.htm. You can find the description of performing a convolution with FFTs in chapter 24: dspguide.com/ch24/7.htm. The book is quite old, but the principles within are immortal. $\endgroup$
    – DrMcCleod
    Mar 4 '19 at 22:14
1
$\begingroup$

Specially on the problems related with PDEs you can find a relatively new article that is using a new approach to solve complex problems and improving the performance of classical approach.

Examples arise in molecular dynamics, micro-mechanics, and turbulent flows. You can find the paper called: Fourier Neural Operator for Parametric PDEs from a recent research pdf , site.

A more detailed view on this new concept here and find more on the paper's references.

$\endgroup$
1
  • $\begingroup$ Maybe just to be clearer, you should also say that their approach uses neural networks. $\endgroup$
    – nbro
    Nov 2 '20 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.