# Discrete Fourier Transform of large data sets

10 views (last 30 days)
Gaby Slavcheva on 1 Jun 2011
Are youa ware of a matlab script that performs DFT on a large set of data, read from a file. My data consists of a number of files (segments) of a signal and I need to obtain the Fourier spectrum of the whole sequence. The file of the whole signal is too large to be fitted into the memory. Is there an algorithm that performs FFT on the segments and reconstructs the spectrum of the whole signal out of the partial spectra?
Many thanks!

Ivan van der Kroon on 1 Jun 2011
Is the size of the result a problem too? Otherwise you can add zeros to a segment perform the transform and in the end take the sum as Fourier transforms are linear. For instance, if S is the number of segments, s the index thereof, N the number of points per segment, n the index thereof, f your signal and F its Fourier transform
F=zeros(S*N,1);
for s=1:S
F = F+fft( [ zeros(N*(s-1),1) ; f ; zeros(N*(S-s),1) ] );
end
If this is a problem too, I would first consider if it is worth the effort. If you have so many data points you will have a very large spectral resolution as well. Is this really needed? I mean, if it is to large to load, you are never going to plot the spectrum even if you manage to get the fft done. So, if not, just load all segments with a fixed number of points skipped, e.g. every 10th entry. Then take the transform of this 'thinned out' signal. Or you can take the mean of these ten points as this single value.
Finally, you could implement your own version of the Cooley-Turkey algorithm. I guess this is the only way to do the entire job. You have to load the data in the same way as my previous suggestion (every n^th entry), perform an fft, save it and load the data again but shifted. Go on until you have passed all the entries. Then perform a weighted sum over all the saved Fourier transforms, with the so-called twiddle factors as weight. From this array, take the fft and this is part of your final vector (it is in the same 'skipped' form). Save this one and do the process again for different twiddle factors until you have all the entries of the final fft. Then you have to reload everything and concatenate the correct entries to get the same segment structure again.
In my opinion, this last option is just not workable because it is to much work for an unhandlable answer, since you will not be able to have this large array in your workspace.
Walter Roberson on 1 Jun 2011
Sounds like "Get a computer with more memory" is the easiest solution ;-)