Non-square FFT
15 ビュー (過去 30 日間)
古いコメントを表示
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 件のコメント
Walter Roberson
2021 年 5 月 11 日
y = nufft(x,t,f) maybe ?? I have no idea what the performace is of nufft()
回答 (1 件)
Matt J
2021 年 5 月 11 日
編集済み: Matt J
2021 年 5 月 11 日
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 件のコメント
Chris Turnes
2021 年 6 月 10 日
編集済み: Walter Roberson
2021 年 6 月 10 日
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)
参考
カテゴリ
Help Center および File Exchange で Fourier Analysis and Filtering についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!