Sparse fast Fourier transform for exactly sparse signals and signals with additive Gaussian noise

In recent years, the Fourier domain representation of sparse signals has been very attractive. Sparse fast Fourier transform (or sparse FFT) is a new technique which computes the Fourier transform in a compressed way, using only a subset of the input data. Sparse FFT computes the desired transform in sublinear time, which means in an amount of time that is smaller than the size of data. In big data problems and medical imaging to reduce the time that patient spends in MRI machine, FFT algorithm is not ‘fast’ enough anymore; therefore, the concept of sparse FFT is very important. Similar to compressed sensing, sparse FFT algorithm computes just the important components in the frequency domain in sublinear time. In this work, sparse FFT algorithm is studied and implemented on MATLAB and its performance is compared with Ann Arbor FFT. A filter is used to hash the frequencies in the n dimensional frequency-sparse signal into B bins, where \(B=n/16\). The filter is used for analyzing an important fraction of the whole signal, and therefore, instead of computing n point FFT, B point FFT is computed, and this results in a faster Fourier transform. The probability of success of the implemented algorithm is investigated for noiseless and noisy signals. It is deduced that as the sparsity increases, the probability of perfect transform also increases. If the performances of the algorithm in both cases are compared, it is clearly seen that the performances degrade when there is noise. Therefore, it can be concluded that the algorithm should be improved especially for noisy considerations. The solvability boundary for a constant probability of error is deducted and added to give insight for future studies.