Non-square FFT
18 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Walter Roberson
el 11 de Mayo de 2021
y = nufft(x,t,f) maybe ?? I have no idea what the performace is of nufft()
Respuestas (1)
Matt J
el 11 de Mayo de 2021
Editada: Matt J
el 11 de Mayo de 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 comentarios
Chris Turnes
el 10 de Jun. de 2021
Editada: Walter Roberson
el 10 de Jun. de 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)
Ver también
Categorías
Más información sobre Fourier Analysis and Filtering en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!