Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price Massachusetts Institute of Technology (MIT)
Abstract
The Discrete Fourier Transform (DFT) is a fundamental tool in signal processing, yet the standard Fast Fourier Transform (FFT) requires $O(n \log n)$ time, which can be prohibitive for large-scale data. This paper introduces a Sparse Fourier Transform (SFT) that computes a $k$-sparse approximation in $O(k \log n)$ time for exactly $k$-sparse signals. By leveraging novel phase-estimation and frequency-domain subtraction techniques, the algorithm achieves near-optimality in both runtime and sample complexity, outperforming the FFT across the entire range of sparsity ($k = o(n)$).
1. Introduction
The Discrete Fourier Transform (DFT) is ubiquitous in modern technology, underpinning everything from media compression to wireless communications. While the Fast Fourier Transform (FFT) revolutionized the field by reducing complexity from $O(n^2)$ to $O(n \log n)$, it still scales with the total signal size $n$. However, many real-world signals are naturally "sparse," meaning they are dominated by a small number $k$ of Fourier coefficients.
Existing sublinear algorithms—those with runtimes proportional to $k$ rather than $n$—have historically faced challenges such as high complexity, large overhead constants, or performance gains limited to extremely sparse signals (e.g., $k < \sqrt{n}$). This work presents a "nearly optimal" SFT that is both theoretically efficient and practically faster than the industry-standard FFTW for any $k < n$.
2. Methodology
The SFT algorithm is built on three core technical pillars designed to achieve sublinear performance without the overhead of previous methods.
2.1 Hashed Binning
The algorithm uses "flat window" filters to hash Fourier coefficients into $B \approx k$ bins. Because the signal is sparse, this hashing process ensures that most bins contain at most one significant ("heavy") coefficient, allowing the algorithm to isolate and process frequencies individually.
2.2 Phase-Based Location
A major bottleneck in sparse transforms is locating the indices of the heavy coefficients. This paper introduces a phase-estimation technique inspired by OFDM wireless technology. By analyzing the phase difference between just two samples of a filtered signal, the algorithm can directly calculate the frequency location. This approach replaces computationally expensive combinatorial "bit-testing" with a direct mathematical estimation, significantly reducing the "Big-Oh" constants.
2.3 Frequency-Domain Updating
To handle multiple coefficients iteratively, the algorithm must subtract identified frequencies from the signal. Traditional methods often perform this in the time domain, which requires a costly non-uniform DFT. Instead, the authors propose subtracting identified coefficients directly from the hashed bins in the frequency domain. This innovation keeps the update step at $O(k)$ complexity, preserving the algorithm's overall efficiency.
3. Results and Complexity Analysis
The authors provide rigorous proofs for the algorithm's performance and sample complexity:
- Runtime (Exactly $k$-sparse): $O(k \log n)$.
- Runtime (General Case): $O(k \log n \log(n/k))$.
- Sample Complexity: The paper proves a lower bound of $\Omega(k \log(n/k) / \log \log n)$, demonstrating that the SFT is nearly optimal in the amount of data required.
3.1 Empirical Benchmarking
In practical tests against FFTW (the "Fastest Fourier Transform in the West"), the SFT showed substantial improvements. For a signal size of $n = 2^{22}$, the proposed algorithm was faster than FFTW for any sparsity $k \le 2^{17}$ (roughly 3% sparsity). In contrast, previous sublinear algorithms only outperformed FFTW when $k$ was less than 2,000 for the same signal size.
4. Conclusion and Future Work
The Nearly Optimal Sparse Fourier Transform represents a significant advancement in signal processing, offering a practical alternative to the FFT for sparse data. The algorithm's success stems from its ability to bypass traditional combinatorial search methods in favor of efficient phase-based estimation. Future research directions include extending the algorithm to non-power-of-two signal lengths and exploring its application to other transforms, such as the Sparse Walsh-Hadamard Transform.
Summary updated