2025/01/21 by Darin Tsui, Tsui, Darin, Kunal Talreja +3
Computer Science · Engineering · Mathematics · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Image and Signal Denoising Methods #Information Theory (cs.IT) #Machine Learning (cs.LG) #Optical Systems and Laser Technology #Statistical and numerical algorithms
paper · pdf · doi:10.48550/arxiv.2501.12365
openalex publication_date 2025/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Computing the Fourier transform of a q-ary function f:ℤqn→ ℝ, 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 ℤq1 × ℤq2 × ⋯ × ℤqn -- where each ℤqi 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=∏i=1n qi → ∞ 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.