0
$\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$
  • $\begingroup$ There was a similar question...You can try to search it. FT doesn't have any application in ML. The only application I can think of is making the data easier for a NN to digest. Neil has some answers on this topic but those are special cases of FT. $\endgroup$ – DuttaA Mar 4 at 20:10
  • $\begingroup$ @DuttaA No, FT has applications in ML, I know. I just don't want to answer to my own question this time. I want people to come up with their ideas (that I don't know of). $\endgroup$ – nbro Mar 4 at 20:48
  • $\begingroup$ for example? I so far cannot imagine any scenario where it would be helpful other than transforming data into a better form. $\endgroup$ – DuttaA Mar 5 at 2:23
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$
  • $\begingroup$ I know all these are possible but if you elaborate a little bit more on the context of AI i.e. The explicit way in which the data after applying FT will be used it'll be great. $\endgroup$ – DuttaA Mar 5 at 9:42
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$
  • $\begingroup$ I was expecting this answer. But, to be precise, what do you mean by "filtering process"? Do you mean the convolution operation using the filters (or kernels)? $\endgroup$ – nbro Mar 4 at 19:07
  • 1
    $\begingroup$ Saying cnn is FT is equivalent to saying dot product is also FT. $\endgroup$ – DuttaA Mar 4 at 20:09
  • $\begingroup$ @nbro Yes, that's right. When implementing the convolutions in a CNN layer, you would usually perform the calculations in frequency space by taking the FT of the kernels and input image, doing a complex multiplication and then taking the inverse FT of the result (unless the kernels are very small in which case it isn't worth it). $\endgroup$ – DrMcCleod Mar 4 at 21:04
  • $\begingroup$ @DrMcCleod Can you point us to an article (or book) which explains this in detail (and possibly emphasises that the process uses FT)? I would like to see the (implementation) details. $\endgroup$ – nbro Mar 4 at 21:17
  • $\begingroup$ @nbro 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 at 22:14

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.