PFT and Auto-MPFT for a Contiguous Subset of Fourier Coefficients

[stumarcus314]

Efficient algorithms have been developed recently to compute a contiguous subset of the Fourier coefficients of a 1D or multidimensional DFT. The 1D version is called the partial Fourier transform (PFT) [1], while the multidimensional version is called the automatic multidimensional partial Fourier transform (Auto-MPFT) [2].

For example, the traditional 1D FFT has complexity O(N*log(N)), while the PFT has complexity O(N+K*log(K)), if only K contiguous Fourier coefficients of the N-point spectrum are required. As another example, the traditional 2D FFT has complexity O(N*log(N)), while the Auto-MPFT has complexity O(N+K*log(K)), where N = N1*N2 and K = K1*K2, if only a K1xK2 contiguous block of the N1xN2 spectrum is required.

Yong-chan Park, one of the authors of those papers, has provided C++ code on GitHub implementing these algorithms. Python implementations are also available on GitHub. Since the IDFT is similar to the DFT, it should be possible to tweak these algorithms to compute a contiguous subset of the time-domain samples of a 1D or multidimensional IDFT.

DFTs and IDFTs requiring only a small contiguous subset of the outputs are common in real world signal processing applications. Would these algorithms be suitable for FFTW?

[1] Park, Yong-chan, Jun-Gi Jang, and U. Kang. "Fast and accurate partial fourier transform for time series data." Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021.

[2] Park, Yong-chan, Jongjin Kim, and U. Kang. "Fast multidimensional partial fourier transform with automatic hyperparameter selection." Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.

Yong-chan Park: https://yongchanpark.github.io/
PFT C++ Code: https://github.com/snudatalab/PFT
Auto-MPFT C++ Code: https://github.com/snudatalab/Auto-MPFT

PFT Python Code: https://github.com/mines-opt-ml/pft-for-ptycho/blob/main/src/PFT1D.py
Auto-MPFT Python Code: https://github.com/mines-opt-ml/pft-for-ptycho/blob/main/src/Auto-MPFT.py

[matteo-frigo]

DFTs and IDFTs requiring only a small contiguous subset of the outputs are common in real world signal processing applications. Would these algorithms be suitable for FFTW?

There is no right answer to this question, but historically we have only focused on exact FFT algorithms where one can mostly ignore the accuracy issue. If we were to extend the scope of FFTW, we would first extend it to exact convolutions, and then to approximate convolutions such as digital filters.

Thanks for the references, which had escaped my attention. It seems to me that [1] has re-invented an old technique. Assume I have a long signal and I only want to compute the lowest-frequency components. One way to accomplish this effect is to run the signal through a low-pass filter, downsample, and then compute the (exact) FFT of the downsampled signal. The problem of filter design has been studied extensively, and one of the possibilities is to reduce it to a minimax polynomial approximation as [1] is doing (see the "Remez-exchange" algorithm or https://ieeexplore.ieee.org/document/149993) Other possibilities exist (e.g. "Kaiser window") to compute a good-enough filter quickly. Depending on whether one cares only about the absolute value of the frequency component, or also about its phase, different techniques are applicable. For example, approximation via rational functions ("IIR" filter) versus polynomials ("FIR" filter) may be acceptable. So it seems to me that [1] is focusing on a single point in a design space that has been well understood for decades. Please let me know if I am misunderstanding the situation.

Either way, a designer needs to be clear about which approximations are acceptable, which seems to be outside the scope of FFTW.