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

Computing the Fourier transform of a q-ary function f:mathbbZqnrightarrow ℝ, 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 mathbbZq1 × mathbbZq2 × cdots × mathbbZqn -- where each mathbbZqi corresponds to integers modulo qi. 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=prodi=1n qi rightarrow ∞ 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(Sn2) and computational complexity of O(Sn2 log N) 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.