LAUSR

The Sparse Fourier Transform (SFT), designed for signals that contain a small number of frequencies, enjoys low complexity, and thus is ideally suited for big data applications. In this paper, we propose Robust Sparse Fourier Transform, (RSFT), which is a modification of SFT that extends the SFT advantages to real world, noisy settings. RSFT can accommodate off-grid frequencies in the data. Furthermore, by incorporating Neyman–Pearson detection in the SFT stages, frequency detection does not require knowledge of the exact sparsity of the signal, and is robust to noise. We analyze the asymptotic performance of RSFT, and study the computational complexity versus detection performance tradeoff. We show that, by appropriately choosing the detection thresholds, the optimal tradeoff can be achieved. We discuss the application of RSFT on short-range ubiquitous radar signal processing and demonstrate its feasibility via simulations.