neural networks can't figure out Fourier transforms? [closed]

Question

I'm trying to understand a few things about neural networks. First, after looking around on the web, it seems that there is no way to compute a (discrete) Fourier transform through a neural network. You can hack it by hard-coding the thing to include the Fourier constants for the transform and then get a decent result. Why can the machine not figure these out by itself?

Answer 1

A DFT is a linear operator. Some neural networks have a sigmoid, RLU, or other non-linear element in the computation path, which might make it harder to simulate a linear operator closely enough.

Added: A full DFT is an N by N matrix multiplication. A neural net has to be big enough to represent that many multiplications (at minimum O(NlogN)).

Answer 2

I think I found a research paper on this topic: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.9688&rep=rep1&type=pdf

It says that "in order to achieve a neural network [that] processes a DFT, a strategy has to be applied which maps the mathematical formula of the DFT to the structure of a neural network", and it seems that they got it to work (section 6).

Answer 3

As I understand it, a neural network is just a classification method that "learns". To solve a problem using neural networks you need:

1. Define the classifier inputs
2. Define the classifier outputs
3. Provide a training set: it is a set of pairs (input, output)
4. Choose a topology (how many layers, how many neurons per layer..) and the function individual neurons will use to convert inputs into outputs

After the neural network is trained, given a new input, the neural network produces an output. How good the output is depends on how "good" was the training. Typically, how representative of the data is the training dataset. This technique can be very useful when attempting to solve classification problems in which there is an unknown relationship between inputs and outputs.

Fast Fourier Transform is just a function. You can have FFT in one dimesion, which is applied to one dimensional phenomena like a sound wave. In this case you pass a vector of values (samples of the intensity of the sound wave) and get back a vector of frequencies. More specifically, the amplitude of harmonics of different frequencies that when composed produce the original sound wave. In two dimensions, FFT takes as input a matrix. For a picture, for example, it could be color intensity at the points in a grid. FFT transforms this into a matrix of harmonics. The length of the vector, or the order of the matrix are given by the sampling rate of the orignal signal.

To apply neural networks to compute FFT:

1. The algorithm to calculate FFT in 1 and 2 dimensions is well defined. Its complexity is O(n log n), which makes it very efficient. The neural network implementation would need to be very efficient (parallelism?) to justify using it.
2. If you change your sampling rate you need to retrain your neural network: let's assume that you have a tained network that calculates FFT for a given sampling rate, if you reduce significantly the sampling rate, the neural network will "overfit" the data, and viceversa.

With all this, I think neural networks can fit very well a specific implementation of FFT as long as the parameters (sampling rate...) do not change.