sFFT-DT: Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse Recovery

Performing FFT using the fact that the underlying signal is sparse has been an item of great interest and several researchers are trying to get the faster algorithm they can ( see the FFT tag) . The following paper is trying to push the envelope. I cannot see an implementation of it listed though. Let us note the use of this approach to perform better localization for the GPS signal.

Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse Recovery by Sung-Hsien Hsieh, Chun-Shien Lu, Soo-Chang Pei

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, researchers at MIT have proposed Sparse Fast Fourier Transform (sFFT) [1][2] as a breakthrough with computational complexity O(K log N) and O(K log N log N/K) for exactly K-sparse signal (with only K non-zero frequency grids) and generally K-sparse signal (with K significant frequency grids), respectively, to outperform classic FFT.

In this paper, a new sparse Fast Fourier Transform by downsampling in the time domain (sFFT-DT) is proposed, based on the assumption that the distribution of the non-zero frequency grids is uniform. The idea behind sFFT-DT is to downsample the original 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 a "moment-preserving problem (MPP)," which is solvable. We prove two theorems related to initializing the downsampling factors under different conditions to have computational complexity, O(K log K) and O(K^(5/4) log K). Moreover, for generally K-sparse signals, solutions to the MPP are inaccurate due to interference from non-significant frequency grids. We observe that significant frequency grids in aliasing are "sparse". This property is exploited, and a new sparse signal recovery algorithm in the context of compressive sensing is presented to refine the solution to MPP. The computational complexity still costs O(K log K) but requires a larger Big-O constant compared to the case of exactly K-sparse signals. We conduct theoretical complexity analyses and simulations to demonstrate that our method (sFFT-DT) outperforms classic FFT and MIT's sFFT.

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.