Abstract
Given a time series vector, how can we efficiently compute a specified part of Fourier coefficients? Fast Fourier transform (FFT) is a widely used algorithm that computes the discrete Fourier transform in many machine learning applications. Despite its pervasive use, all known FFT algorithms do not provide a fine-tuning option for the user to specify one's demand, that is, the output size (the number of Fourier coefficients to be computed) is algorithmically determined by the input size. This matters because not every application using FFT requires the whole spectrum of the frequency domain, resulting in an inefficiency due to extra computation. In this paper, we propose a fast Partial Fourier Transform (PFT), a careful modification of the Cooley-Tukey algorithm that enables one to specify an arbitrary consecutive range where the coefficients should be computed. We derive the asymptotic time complexity of PFT with respect to input and output sizes, as well as its numerical accuracy. Experimental results show that our algorithm outperforms the state-of-the-art FFT algorithms, with an order of magnitude of speedup for sufficiently small output sizes without sacrificing accuracy.
Introduction
The Discrete Fourier Transform (DFT) is a cornerstone of modern signal processing, essential for tasks ranging from image compression to anomaly detection. While the standard Fast Fourier Transform (FFT) significantly reduced computational costs from $O(N^2)$ to $O(N \log N)$, it remains an "all-or-nothing" algorithm. In many practical scenarios, such as low-pass filtering or targeted frequency analysis, only a small subset of the frequency spectrum is required. Standard FFT implementations force the computation of the entire spectrum, leading to unnecessary overhead.
The Fast Partial Fourier Transform (PFT) addresses this flexibility gap. By modifying the classic Cooley-Tukey algorithm, PFT allows users to compute a specific, consecutive range of $M$ Fourier coefficients for an input of size $N$, achieving a complexity of $O(N + M \log M)$.
Methodology
The PFT algorithm is built upon three primary technical innovations:
- Twiddle Factor Approximation: The Cooley-Tukey decomposition involves "twiddle factors" (complex roots of unity). PFT identifies that for narrow output ranges, many twiddle factors oscillate slowly. These are replaced with minimax polynomial approximations to reduce computational load.
- Base Exponential Functions: To maintain efficiency, the algorithm utilizes precomputed "base exponential functions." These data-independent constants are rescaled at runtime to match the user's requested frequency range.
- Summation Reordering: By reordering summation steps, PFT separates data-independent factors from data-dependent ones. The final architecture involves executing smaller FFTs followed by linear pre- and post-processing.
This approach allows for controllable accuracy, where users can trade a negligible amount of numerical precision for significant speed gains.
Experimental Setup
The performance of PFT was evaluated against state-of-the-art libraries, including FFTW and Intel MKL, using both synthetic and real-world datasets.
The synthetic data spanned sizes from $2^{12}$ to $2^{22}$, while real-world datasets included urban sound recordings and air conditioning sensor time series. Notably, PFT does not strictly require power-of-two input sizes, performing well on any "b-smooth" number.
Key Results and Discussion
Experimental results demonstrate that PFT provides substantial performance improvements when the target output size $M$ is significantly smaller than the input size $N$.
As shown in the figures above, PFT achieved up to a 21x speedup on synthetic data and maintained an 8.8x speedup on real-world sensor data. Accuracy remains high, with relative $\ell_2$ errors typically below $10^{-6}$.
Practical Insights
- Efficiency Threshold: PFT is most effective when $M \ll N$. If $M$ approaches $N$, the overhead of polynomial approximation and reordering may exceed the cost of a standard, highly optimized FFT.
- Anomaly Detection: In a practical application, PFT was used to extract low-frequency trends for anomaly detection. It produced identical results to standard FFT-based methods but in a fraction of the time.
Limitations and Future Work
While PFT offers a significant theoretical and practical advantage, its performance is currently sensitive to the choice of the divisor $p$ used for input splitting. Future research aims to automate this hyperparameter tuning. Additionally, while PFT outperforms standard libraries in general-purpose execution, further low-level hardware optimization (e.g., AVX instructions) could further widen the performance gap against established libraries like Intel MKL.
Summary updated