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

arXiv: https://arxiv.org/abs/2501.12365 · HTML: https://mlsanity.com/paper/2501.12365/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 35 references that are in the map.
- First posted on arXiv 21 Jan 2025.

## Builds on (most cited first, 6 of 6)

- [A Scalable Walsh-Hadamard Regularizer to Overcome the Low-degree Spectral Bias of Neural Networks](https://mlsanity.com/paper/2305.09779/) (2023)
- [On Recovering Higher-order Interactions from Protein Language Models](https://mlsanity.com/paper/2405.06645/) (2024)
- [A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain](https://mlsanity.com/paper/1310.1803/) (2013)
- [Efficiently Computing Sparse Fourier Transforms of q-ary Functions](https://mlsanity.com/paper/2301.06200/) (2023)
- [Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform](https://mlsanity.com/paper/1504.07648/) (2015)
- [Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions](https://mlsanity.com/paper/1303.1209/) (2013)

## Abstract (arXiv)

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.