Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-04T23:20:26.887Z
Answers.LastActivityDate: 2019-03-04T23:20:26.887Z
Answers.UserDisplayName: Douglas Daseeco
Answers.Body: <p>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.</p>
  
  <p>The algorithm for using Fourier Transforms to calculate a convolution between an image and a filter kernel is as follows:</p>
  
  <p>Assuming a 100x100 input image, and a 3x3 filter kernel (such as a <a href="https://en.wikipedia.org/wiki/Sobel_operator" rel="nofollow noreferrer">Sobel Edge-Detection filter</a>).</p>
  
  <ol>
  <li>Calculate the 2D Fourier Transform (FT) of the image (<a href="http://www.fftw.org/" rel="nofollow noreferrer">C library</a>, <a href="https://docs.scipy.org/doc/numpy-1.13.0/reference/routines.fft.html" rel="nofollow noreferrer">Python library</a>)</li>
  <li><p>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:</p>
  
  <ul>
  <li>a -> (99, 99)    //bottom right</li>
  <li>b -> (0, 99)     //bottom left</li>
  <li>c -> (1, 99)</li>
  <li>d -> (99, 0) //top right</li>
  <li>e -> (0, 0) //top left</li>
  <li>f -> (1, 0)   </li>
  <li>g -> (99, 1)</li>
  <li>h -> (0, 1)</li>
  <li>i -> (1, 1)</li>
  </ul>
  
  <p>Set all the other padded filter kernel pixels to zero</p></li>
  <li><p>Calculate the 2D Fourier Transform of the padded filter kernel.</p></li>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  </ol>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-04T22:14:41.493Z
Answers.Text: For a general overview of digital signal processing (including image processing), I recommend http://www.dspguide.com/pdfbook.htm. You can find the description of performing a convolution with FFTs in chapter 24: http://www.dspguide.com/ch24/7.htm. The book is quite old, but the principles within are immortal.
Answers.UserDisplayName: DrMcCleod
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-04T19:04:35.937Z
Answers.LastActivityDate: 2019-03-06T09:18:29.177Z
Answers.LastEditDate: 2019-03-06T09:18:29.177Z
Answers.UserDisplayName: DrMcCleod
Answers.Body: <p>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.</p>
  <p>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 <a href="https://arxiv.org/pdf/2010.08895v1.pdf" rel="nofollow noreferrer">pdf</a> , <a href="https://arxiv.org/abs/2010.08895v1" rel="nofollow noreferrer">site</a>.</p>
  <p>A more detailed view on this new concept <a href="https://www.technologyreview.com/2020/10/30/1011435/ai-fourier-neural-network-cracks-navier-stokes-and-partial-differential-equations/" rel="nofollow noreferrer">here</a> and find more on the paper's references.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-02T21:37:58.680Z
Answers.Text: Maybe just to be clearer, you should also say that their approach uses neural networks.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-02T15:12:40.833Z
Answers.LastActivityDate: 2020-11-02T15:19:20.483Z
Answers.LastEditDate: 2020-11-02T15:19:20.483Z
Answers.UserDisplayName: mario ruiz
Body: <p>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. <a href="https://math.stackexchange.com/a/11114/168764">this answer</a> or <a href="https://www.youtube.com/watch?v=mkGsMWi_j4Q" rel="nofollow noreferrer">this</a> and <a href="https://www.youtube.com/watch?v=spUNpyF58BY" rel="nofollow noreferrer">this</a> Youtube videos.</p>
  
  <p>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.</p>
  
Tags: <machine-learning><applications><robotics><fourier-transform>
Title: What are examples of applications of the Fourier transform to AI?
UserDisplayName: nbro
ThreadText: # What are examples of applications of the Fourier transform to AI?
  
  (Asked by: username_0 on 2019-03-04)
  
  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](https://math.stackexchange.com/a/11114/168764) or [this](https://www.youtube.com/watch?v=mkGsMWi_j4Q) and [this](https://www.youtube.com/watch?v=spUNpyF58BY) 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.
  
  **Tags:** machine-learning, applications, robotics, fourier-transform
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-03-04. Score: 1
  
  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.
  
  
  ---
  
  ### Answer by username_2 on 2019-03-04. Score: 1
  
  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](https://en.wikipedia.org/wiki/Sobel_operator)).
  
  1. Calculate the 2D Fourier Transform (FT) of the image ([C library](http://www.fftw.org/), [Python library](https://docs.scipy.org/doc/numpy-1.13.0/reference/routines.fft.html))
  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.
  
  > **Comments:**
  > **username_2**: For a general overview of digital signal processing (including image processing), I recommend http://www.dspguide.com/pdfbook.htm. You can find the description of performing a convolution with FFTs in chapter 24: http://www.dspguide.com/ch24/7.htm. The book is quite old, but the principles within are immortal.  
  
  ---
  
  ### Answer by username_3 on 2020-11-02. Score: 1
  
  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](https://arxiv.org/pdf/2010.08895v1.pdf) , [site](https://arxiv.org/abs/2010.08895v1).
  
  A more detailed view on this new concept [here](https://www.technologyreview.com/2020/10/30/1011435/ai-fourier-neural-network-cracks-navier-stokes-and-partial-differential-equations/) and find more on the paper's references.
  
  > **Comments:**
  > **username_0**: Maybe just to be clearer, you should also say that their approach uses neural networks.  
  
  ---
  
  