标题： 广义$q$-元函数的稀疏傅里叶变换的高效算法 显示英文标题

标题： Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions

摘要： 计算一个$q$-元函数的傅里叶变换$f:\mathbb{Z}_{q}^n\rightarrow \mathbb{R}$，该函数将$q$-元序列映射到实数，是数学中的一个重要问题，在生物学、信号处理和机器学习中有广泛的应用。 先前的研究表明，在稀疏性假设下，可以使用快速且样本高效的算法有效地计算傅里叶变换。 然而，在大多数实际情况下，该函数定义在一个更一般的空间——广义$q$-元序列空间$\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \times \mathbb{Z}_{q_n}$——其中每个$\mathbb{Z}_{q_i}$对应于模$q_i$的整数。 在此，我们开发了GFast，一种编码理论算法，该算法计算$S$-稀疏傅里叶变换的$f$，其样本复杂度为$O(Sn)$，计算复杂度为$O(Sn \log N)$，失败概率随着$N=\prod_{i=1}^n q_i \rightarrow \infty$趋近于零，其中$S = N^\delta$对于某些$0 \leq \delta < 1$。 我们证明了噪声鲁棒版本的GFast在相同的高概率保证下，以样本复杂度$O(Sn^2)$和计算复杂度$O(Sn^2 \log N)$来计算变换。 此外，我们展示了GFast在合成实验中使用$16\times$更少的样本，能够更快地计算广义$q$-元函数$8\times$的稀疏傅里叶变换，并且与现有的傅里叶算法相比，在使用最多$13\times$更少的样本的情况下，能够解释现实世界的心脏病诊断和蛋白质适应性模型，这些模型应用了作为$q$-元函数的最有效参数化方法。 显示英文摘要

摘要： Computing the Fourier transform of a $q$-ary function $f:\mathbb{Z}_{q}^n\rightarrow \mathbb{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 $\mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots \times \mathbb{Z}_{q_n}$ -- where each $\mathbb{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 \log N)$, and a failure probability that approaches zero as $N=\prod_{i=1}^n q_i \rightarrow \infty$ with $S = N^\delta$ for some $0 \leq \delta < 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 \log N)$ under the same high probability guarantees. Additionally, we demonstrate that GFast computes the sparse Fourier transform of generalized $q$-ary functions $8\times$ faster using $16\times$ fewer samples on synthetic experiments, and enables explaining real-world heart disease diagnosis and protein fitness models using up to $13\times$ fewer samples compared to existing Fourier algorithms applied to the most efficient parameterization of the models as $q$-ary functions.