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

Darin Tsui, Kunal Talreja, Amirali Aghazadeh

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

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},
}
Figure