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

Code

• github.com/amirgroup-codes/gfast
  OfficialIn paperpytorch★ 2

Abstract

Computing the Fourier transform of a q-ary function f:Z_q^n 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 Z_q_1 Z_q_2 Z_q_n -- where each 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 N), and a failure probability that approaches zero as N=_i=1^n q_i 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^2) and computational complexity of O(Sn^2 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.

Reproductions