TL;DR
This paper introduces FPS-SFT, a novel multi-dimensional sparse Fourier transform that leverages the Fourier projection-slice theorem. By taking Fourier transforms along randomly oriented lines in the data, FPS-SFT efficiently reconstructs sparse signals in frequency domains, outperforming existing methods, especially for clustered or less sparse data.
What Problem Does This Paper Address?
Traditional multi-dimensional Fourier transforms, like the Fast Fourier Transform (FFT), are computationally expensive, scaling poorly with data size. While sparse Fourier transforms (SFTs) offer a solution by exploiting signal sparsity in the frequency domain, existing multi-dimensional SFTs have limitations. Specifically, the SFT proposed in [2] is restricted to 2D data with equal dimensions and struggles with signals that are not extremely sparse or have clustered frequencies. This paper addresses the need for a more general and robust multi-dimensional SFT that can handle arbitrary dimensions, varying sparsity levels, and clustered frequency distributions, while maintaining low sample and computational complexity.
Methods
The core innovation is the FPS-SFT (Fourier Projection-Slice Sparse Fourier Transform). It's inspired by the Fourier projection-slice theorem, which states that the Fourier transform of a projection of an object is a slice of the object's Fourier transform.
Here's how it works:
- Random Lines: Instead of just using rows and columns (like in [2]), FPS-SFT takes 1D Discrete Fourier Transforms (DFTs) along lines with random slopes and offsets within the multi-dimensional data.
- Projections: The 1D DFTs along these lines are interpreted as projections of the multi-dimensional DFT of the signal.
- Sparsity Exploitation: The algorithm leverages the signal's sparsity in the frequency domain. If a projection (a DFT along a line) results in a "1-sparse" bin (meaning only one significant frequency contributes to that bin), the frequency can be decoded.
- Iterative Recovery: FPS-SFT works iteratively. In each iteration, it recovers a subset of significant frequencies. The contribution of these recovered frequencies is then removed from the signal, making the signal sparser for subsequent iterations. This progressive recovery helps avoid deadlocks that plague other SFT methods.
- Orthogonal and Uniform Projections: The paper introduces specific designs for line lengths and slopes (Lemmas 1 and 2) to ensure that projections are orthogonal and uniform. This minimizes frequency collisions and increases the probability of obtaining 1-sparse bins, even for less sparse or clustered signals.
- Multi-dimensional Extension: The framework is generalized to D-dimensional data by extending the concept of random lines and using the Least Common Multiple (LCM) for line lengths.
Datasets
The paper uses simulated data for evaluating the performance of FPS-SFT against existing methods. For the sparse image reconstruction application, a publicly available brain MRI image from [12] is used.
Key Insights and Ideas
- Randomness is Key: Randomly choosing the orientation of the lines for DFTs is crucial. It breaks the rigid structure of row/column projections and significantly improves the ability to resolve frequencies, especially when they are clustered or the signal is less sparse.
- Projection-Slice Theorem as a Blueprint: The paper elegantly connects the signal processing task to a fundamental theorem in image reconstruction, providing a theoretical basis for the approach.
- Iterative Sparsification: The "construction-subtraction" approach, where recovered frequencies are removed from the signal, is a clever way to continuously enhance sparsity and simplify subsequent recovery steps.
- Generalizability: The method is not limited to 2D or specific data sizes, making it applicable to a broader range of multi-dimensional signal processing problems.
Key Results
- Improved Recovery Probability: FPS-SFT demonstrates a significantly higher probability of perfect frequency recovery compared to the SFT of [2], especially for moderately sparse signals (K = 2N₀) and clustered frequencies. For instance, with uniform frequencies, FPS-SFT achieves ~96% recovery for K=5N₀.
- Reduced Sample Complexity: FPS-SFT requires fewer samples for perfect recovery, particularly for sparser signals. For K=N₀, it uses only ~5.9% of the samples in uniform or clustered cases.
- Sparse Image Reconstruction: The method successfully reconstructs sparse images from undersampled frequency domain data, achieving near-perfect reconstruction for images with up to 6.6% non-zero pixels using 70.3% of the frequency samples.
- Complexity: The sample complexity is O(L) and computational complexity is O(L log L + K), where L is the LCM of dimension lengths and K is the number of sparse frequencies. This achieves the lower bounds for SFT algorithms when K is proportional to L.
Limitations and Future Work
- Maximum Iterations: The paper notes that if the number of significant frequencies (K) is very large, the algorithm might require a high number of iterations (Tmax) to achieve perfect recovery, potentially approaching full sampling. The simulations were limited by a set Tmax.
- Noise and Off-Grid Frequencies: While the paper focuses on sparse signals, the abstract mentions an extension to noisy signals with off-grid frequencies, suggesting this as a direction for future work.
- Theoretical Guarantees for Clustered Frequencies: While empirical results show good performance for clustered frequencies, the theoretical analysis primarily focuses on uniformly distributed frequencies. Further theoretical investigation into the performance with clustered frequencies would be valuable.
Summary updated