Introduction
Computing the Fourier transform of functions defined over discrete sequences is a fundamental task in signal processing, machine learning, and computational biology. For a function $f: \mathbb{Z}_q^n \to \mathbb{R}$, the Fourier transform reveals the underlying frequency components, which often correspond to interactions between input features. In many practical scenarios, these functions are "sparse," meaning only a small number of Fourier coefficients are significantly non-zero.
While Sparse Fourier Transform (SFT) algorithms have been developed for $q$-ary functions where all input dimensions have the same size $q$, real-world data is rarely so uniform. Categorical features in medical datasets or amino acid positions in protein sequences often have varying alphabet sizes. Existing methods typically handle this by padding all dimensions to the maximum size $q_{max}$, which introduces a significant "dimensionality tax"—an exponential increase in the search space and sample requirements. This paper introduces GFast, a coding-theoretic algorithm designed to compute the SFT of generalized $q$-ary functions directly, bypassing the inefficiencies of uniform padding.
The GFast Algorithm
GFast (and its noise-robust variant, NR-GFast) leverages a framework inspired by sparse graph codes and the FFAST (Fast Fourier Aliasing-based Sparse Transform) architecture. The algorithm operates through three primary stages:
1. Subsampling and Aliasing
The algorithm begins by subsampling the function in the time domain using specific patterns. This process induces "aliasing" in the frequency domain, where the total energy of the Fourier coefficients is distributed into a smaller number of "bins." By carefully choosing the subsampling periods, the algorithm ensures that the mapping from coefficients to bins follows a structure that can be decoded.
2. Bin Detection and Identification
Using a set of time-domain offsets (delays), GFast analyzes each bin to determine its content. Bins are classified into three types:
- Zero-tons: Bins containing no significant Fourier coefficients.
- Singletons: Bins containing exactly one significant coefficient. For singletons, the algorithm uses phase information from the delayed samples to recover both the index (frequency) and the value of the coefficient.
- Multi-tons: Bins where multiple coefficients have collided.
3. The Peeling Decoder
The recovery process is modeled as a decoding problem on a bipartite graph. Once a singleton is identified, its value is recorded, and its contribution is "peeled" (subtracted) from all other bins where that coefficient aliased. This removal potentially transforms multi-tons into new singletons, allowing the process to iterate until all $S$ significant coefficients are recovered.
Theoretical and Practical Performance
A key challenge in generalized $q$-ary spaces is that the resulting factor graph is inherently "uneven" or irregular, as different dimensions contribute different degrees to the graph. The authors prove that despite this asymmetry, the peeling decoder converges with high probability as the total space size $N = \prod q_i$ approaches infinity.
GFast achieves a sample complexity of $O(Sn)$ and a computational complexity of $O(Sn \log N)$. For the noise-robust version, NR-GFast, the complexities are $O(Sn^2)$ and $O(Sn^2 \log N)$, respectively. These bounds represent a significant improvement over standard Fast Fourier Transform (FFT) approaches, which require $O(N \log N)$ operations, especially when the sparsity $S$ is much smaller than $N$.
Experimental Evaluation
The authors validated GFast across synthetic and real-world datasets, demonstrating its efficiency in practical applications:
- Synthetic Benchmarks: In large-scale tests ($n=20$), GFast demonstrated an $8\times$ speedup in computation and required $16\times$ fewer samples than the previous state-of-the-art $q$-SFT algorithm to achieve the same error threshold.
- Heart Disease Diagnosis: Using a dataset from the UCI Machine Learning Repository, GFast was used to interpret a multilayer perceptron (MLP) trained on 12 categorical features. It successfully identified the most influential feature interactions using significantly fewer samples than traditional methods.
- Protein Fitness Modeling: The algorithm was applied to a Green Fluorescent Protein (GFP) dataset to predict protein fluorescence based on mutations. NR-GFast enabled the explanation of these complex biological models using up to $13\times$ fewer samples than existing Fourier-based explainability tools.
Conclusion
GFast addresses a critical gap in sparse signal processing by extending efficient Fourier recovery to generalized $q$-ary functions. By avoiding the overhead of uniform alphabet padding, it provides a scalable solution for interpreting high-dimensional categorical models in biology and medicine. Future work includes extending the algorithm to handle even larger alphabet sizes and exploring its use in regularizing neural networks during training.
Summary updated