Non-square FFT
15 views (last 30 days)
Show older comments
Hello,
I wonder if one can perform a non-square DFT efficiently. Specifically, let's say I've got a grid function with N = 2 * K points, and I want to find the lower half (by frequency magnitude) of its DFT only. An obvious way would be to perform an FFT of the input grid function and then throw away the K higher frequency components. I wonder if there is a faster way to obtain the same result.
Thanks,
Dmitry
2 Comments
Walter Roberson
on 11 May 2021
y = nufft(x,t,f) maybe ?? I have no idea what the performace is of nufft()
Answers (1)
Matt J
on 11 May 2021
Edited: Matt J
on 11 May 2021
There's probably no significant efficiency to be gained if you just want to get rid of half of the frequencies, as in the example you've mentioned. For a highly sparse FFT, for example if you want just want to keep the first 3 out of 1000 frequencies, it makes sense to pre-compute a non-square DFT matrix,
n=1000;
M=exp(-1j *(2*pi/n)* (0:n-1).*(0:2).'); % 3xn DFT matrix
and multiply it with your signal.
7 Comments
Chris Turnes
on 10 Jun 2021
Edited: Walter Roberson
on 10 Jun 2021
Another option is to use the Chirp-Z Transform to compute a partial FFT, though for simple cases FFT + throw away is still probably more efficient.
However, if you have a simple division like wanting only the first half of the frequency vector, you could always apply the same recursion rules that the FFT itself does and just do two smaller FFTs, summing the result.
For instance, for a length-100 signal, if you only want the first 50 coefficients of the FFT you could do
x = randn(100,1);
% FFT + throw away.
y1 = fft(x);
y1 = y1(1:50);
% Manually compute two FFTs.
y2 = fft(x(1:2:end)) + exp(-1j*2*pi/100*(0:49)') .* fft(x(2:2:end));
norm(y1-y2)
See Also
Categories
Find more on Fourier Analysis and Filtering in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!