Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions

Darin Tsui, Kunal Talreja, Amirali Aghazadeh

TL;DR

GFast is a new coding-theoretic algorithm designed to compute the sparse Fourier transform of functions with mixed-size discrete inputs (generalized $q$-ary functions). By directly handling non-uniform alphabet sizes, GFast avoids the "dimensionality tax" of existing methods, achieving up to $16\times$ better sample efficiency and $8\times$ faster computation in practical biological and machine learning applications.

What Problem Does This Paper Address?

In many fields like biology (protein sequences) and machine learning (categorical features), we work with functions that map discrete sequences to real numbers. Often, these functions are "sparse" in the frequency domain, meaning only a few Fourier coefficients carry most of the information.

While algorithms exist to compute the Sparse Fourier Transform (SFT) for "q-ary" functions (where every input has the same number of categories $q$), real-world data is rarely that uniform. For example, a medical model might have features for "Sex" (2 categories), "Age Group" (10 categories), and "Chest Pain Type" (4 categories).

Existing algorithms force a "one-size-fits-all" approach, treating every feature as if it had the maximum number of categories ($q_{max}$). This naively inflates the search space—for a protein model, this can mean the difference between searching a space of $10^{10}$ vs $10^{12}$ points. The authors address this gap by creating an algorithm that operates directly on these "generalized" $q$-ary spaces without unnecessary padding.

Methods

The authors introduce GFast (and its noise-robust version, NR-GFast). The algorithm is built on a coding-theoretic framework, specifically inspired by sparse graph codes and the FFAST architecture. It operates in three main stages:

  1. Subsampling and Aliasing: The algorithm strategically samples the function in the time domain. This causes "aliasing" in the frequency domain, where multiple Fourier coefficients are summed together into "bins."
  2. Bin Detection: Using a set of offsets (delays), the algorithm identifies which bins contain zero coefficients ("zero-tons"), exactly one coefficient ("singletons"), or multiple ("multi-tons"). For singletons, it uses the phase information to recover the coefficient's index and value.
  3. Peeling Decoder: This is the "aha" moment of the algorithm. It treats the recovery process as a bipartite graph problem. Once a singleton is identified and recovered, its contribution is "peeled" (subtracted) from all other bins it influenced. This process repeats until all significant coefficients are recovered.

The core technical contribution is proving that even though mixed alphabet sizes create an "uneven" graph (where nodes have different degrees), the peeling decoder still converges with high probability.

Datasets

The authors evaluated GFast using three primary sources:

  • Synthetic Data: Large-scale experiments with $n=20$ length sequences and varying alphabet sizes to test scaling and noise robustness.
  • Heart Disease Diagnosis: A dataset from the UCI Machine Learning Repository containing 12 categorical features used to train a multilayer perceptron (MLP).
  • Protein Fluorescence: A dataset of Green Fluorescent Protein (GFP) sequences. The model predicts protein fitness (fluorescence) based on mutations at 12 specific sites.

Key Insights and Ideas

  • Direct Parameterization Matters: The "workaround" of padding alphabets to a uniform size $q_{max}$ isn't just a minor inconvenience; it leads to an exponential increase in the samples required to "explain" a model.
  • Graph Asymmetry is Manageable: In standard coding theory, regular graphs (where every node has the same number of edges) are preferred for simplicity. GFast proves that the "uneven degree distribution" inherent in generalized $q$-ary functions does not degrade the algorithm's performance guarantees in the asymptotic regime.
  • Sample Complexity vs. Sparsity: GFast achieves a sample complexity of $O(Sn)$, where $S$ is sparsity and $n$ is the number of features. This is significantly better than the $O(N \log N)$ of a standard FFT when the signal is sparse.

Key Results

  • Speed and Efficiency: On synthetic experiments, GFast was $8\times$ faster and required $16\times$ fewer samples than the previous state-of-the-art ($q$-SFT) to reach the same error threshold.
  • Real-World Explainability: When used to interpret "black-box" neural networks for heart disease and protein fitness, NR-GFast required $13\times$ fewer samples than existing Fourier-based explainability methods.
  • Noise Robustness: The NR-GFast variant maintained high accuracy even in the presence of additive Gaussian noise, with a sample complexity of $O(Sn^2)$.

Limitations and Future Work

  • Bounded Alphabet Size: The current theoretical analysis and experiments assume relatively small alphabet sizes (up to $q=12$). The authors note that performance may degrade if $q$ reaches the thousands (e.g., in some Natural Language Processing tasks).
  • Sparsity Assumption: Like all SFT algorithms, GFast relies on the function being truly sparse in the Fourier domain. If the "energy" is spread across many coefficients, the peeling decoder may fail.
  • Future Directions: The authors suggest extending GFast to handle even larger-scale machine learning models and exploring its use in regularizing neural networks during the training phase itself.

Summary updated

Abstract

Computing the Fourier transform of a $q$-ary function $f:\mathbb{Z}_{q}^n\rightarrow \mathbb{R}$, which maps $q$-ary sequences to real numbers, is an important problem in mathematics with wide-ranging applications in biology, signal processing, and machine learning. Previous studies have shown that, under the sparsity assumption, the Fourier transform can be computed efficiently using fast and sample-efficient algorithms. However, in most practical settings, the function is defined over a more general space -- the space of generalized $q$-ary sequences $\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \times \mathbb{Z}_{q_n}$ -- where each $\mathbb{Z}_{q_i}$ corresponds to integers modulo $q_i$. Herein, we develop GFast, a coding theoretic algorithm that computes the $S$-sparse Fourier transform of $f$ with a sample complexity of $O(Sn)$, computational complexity of $O(Sn \log N)$, and a failure probability that approaches zero as $N=\prod_{i=1}^n q_i \rightarrow \infty$ with $S = N^\delta$ for some $0 \leq \delta < 1$. We show that a noise-robust version of GFast computes the transform with a sample complexity of $O(Sn^2)$ and computational complexity of $O(Sn^2 \log N)$ under the same high probability guarantees. Additionally, we demonstrate that GFast computes the sparse Fourier transform of generalized $q$-ary functions $8\times$ faster using $16\times$ fewer samples on synthetic experiments, and enables explaining real-world heart disease diagnosis and protein fitness models using up to $13\times$ fewer samples compared to existing Fourier algorithms applied to the most efficient parameterization of the models as $q$-ary functions.
BibTeX
@inproceedings{tsui2025efficient,
  author = {Darin Tsui and Kunal Talreja and Amirali Aghazadeh},
  title = {{Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions}},
  booktitle = {ITW},
  year = {2025},
  doi = {10.1109/itw62417.2025.11240519},
}

Loading related content...

Figure