2017/06/14 by Matteo Briani, Briani, Matteo, Annie Cuyt +3
Computer Science · Engineering · #65T50 #Direction-of-Arrival Estimation Techniques #FOS: Mathematics #Image and Signal Denoising Methods #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1706.04520
openalex publication_date 2017/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The FFT algorithm that implements the discrete Fourier transform is considered one of the top ten algorithms of the 20th century. Its main strengths are the low computational cost of O(n log n) and its stability. It is one of the most commonly used algorithms to analyze signals with a dense frequency representation. In recent years there has been an increasing interest in sparse signal representations and a need for algorithms that exploit such structure. We propose a new technique that combines the properties of the discrete Fourier transform with the sparsity of the signal. This is achieved by integrating ideas of Prony's method into Fourier's method. The resulting technique has the same frequency resolution as the original FFT algorithm but uses fewer samples and can achieve a lower computational cost. Moreover, the proposed algorithm is well suited for a parallel implementation.