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:{\mathbb{Z}}_q^n\to \mathbb{R}$, which maps $q$-ary sequences to real numbers, is an important problem in mathemati…