Papers › Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions
Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions
Darin Tsui, Kunal Talreja, Amirali Aghazadeh
Computing the Fourier transform of a q-ary function f:ℤ_qⁿ→ℝ, 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 ℤ_(q₁) ×ℤ_(q₂) ×⋯×ℤ_(qₙ) -- where each ℤ_(qᵢ) corresponds to integers modulo qᵢ. 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 logN), and a failure probability that approaches zero as N=∏ᵢ₌₁ⁿ qᵢ →∞ with S = N^δ for some 0 ≤δ< 1. We show that a noise-robust version of GFast computes the transform with a sample complexity of O(Sn²) and computational complexity of O(Sn² logN) under the same high probability guarantees. Additionally, we demonstrate that GFast computes the sparse Fourier transform of generalized q-ary functions 8× faster using 16× fewer samples on synthetic experiments, and enables explaining real-world heart disease diagnosis and protein fitness models using up to 13× fewer samples compared to existing Fourier algorithms applied to the most efficient parameterization of the models as q-ary functions.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections