A Combinatorial Aliasing-Based Sparse Fourier Transform

作者：Qiu, Pengcheng^*; Yu, Feng

来源：IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2015, E98A(9): 1968-1972.

DOI：10.1587/transfun.E98.A.1968

• sparse Fourier transform
• Chinese remainder theorem
• aliasing
• noise robustness

The sparse Fourier transform (SFT) seeks to recover k non-negligible Fourier coefficients from a k-sparse signal of length N (k << N). A single frequency signal can be recovered via the Chinese remainder theorem (CRT) with sub-sampled discrete Fourier transforms (DFTs). However, when there are multiple non-negligible coefficients, more of them may collide, and multiple stages of sub-sampled DFTs are needed to deal with such collisions. In this paper, we propose a combinatorial aliasing-based SFT (CASFT) algorithm that is robust to noise and greatly reduces the number of stages by iteratively recovering coefficients. First, CASFT detects collisions and recovers coefficients via the CRT in a single stage. These coefficients are then subtracted from each stage, and the process iterates through the other stages. With a computational complexity of O(k log k log(2) N) and sample complexity of O(k log(2) N), CASFT is a novel and efficient SFT algorithm.

• 出版日期2015-9
• 单位浙江大学