2014/07/31 by Sung-Hsien Hsieh, Hsieh, Sung-Hsien, Chun-Shien Lu +4
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Analysis and Transform Methods #Sparse and Compressive Sensing Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1407.8315
31 pages, 6 figures, the preliminary version was published in ICASSP 2013
openalex publication_date 2014/07/31 · arxiv created 2015/05/22 · arxiv updated 2015/05/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Fast Fourier Transform (FFT) is one of the most important tools in digital signal processing. FFT costs O(N log N) for transforming a signal of length N. Recently, Sparse Fourier Transform (SFT) has emerged as a critical issue addressing how to compute a compressed Fourier transform of a signal with complexity being related to the sparsity of its spectrum. In this paper, a new SFT algorithm is proposed for both exactly K-sparse signals (with K non-zero frequencies) and generally K-sparse signals (with K significant frequencies), with the assumption that the distribution of the non-zero frequencies is uniform. The nuclear idea is to downsample the input signal at the beginning; then, subsequent processing operates under downsampled signals, where signal lengths are proportional to O(K). Downsampling, however, possibly leads to "aliasing." By the shift property of DFT, we recast the aliasing problem as complex Bose-Chaudhuri-Hocquenghem (BCH) codes solved by syndrome decoding. The proposed SFT algorithm for exactly K-sparse signals recovers 1-τfrequencies with computational complexity O(K log K) and probability at least 1-O(\fraccτ)τK under K=O(N), where c is a user-controlled parameter. For generally K-sparse signals, due to the fact that BCH codes are sensitive to noise, we combine a part of syndrome decoding with a compressive sensing-based solver for obtaining K significant frequencies. The computational complexity of our algorithm is max ( O(K log K), O(N) ), where the Big-O constant of O(N) is very small and only a simple operation involves O(N). Our simulations reveal that O(N) does not dominate the computational cost of sFFT-DT.