A structured review of sparse fast Fourier transform algorithms

Discrete Fourier transform (DFT) implementation requires high computational resources and time; a computational complexity of order O (N-2) for a signal of size N. Fast Fourier transform (FFT) algorithm, that uses butterfly structures, has a computational complexity of O(Nlog(N)), a value much less than O (N-2). However, in recent years by introducing big data in many applications, FFT calculations still impose serious challenges in terms of computational complexity, time requirement, and energy consumption. Involved data in many of these applications are sparse in the spectral domain. For these data by using Sparse Fast Fourier Transform (SFFT) algorithms with a sub-linear computational and sampling complexity, the problem of computational complexity of Fourier transform has been reduced substantially. Different algorithms and hardware implementations have been introduced and developed for SFFT calculations. This paper presents a categorized review of SFFT, highlights the differences of its various algorithms and implementations, and also reviews the current use of SFFT in different applications. (C)& nbsp;2022 Elsevier Inc. All rights reserved.

Automated summary

Implementing discrete Fourier transform (DFT) requires high computational resources and time. Fast Fourier transform (FFT) algorithm has a lower computational complexity than DFT, but still faces challenges with big data. Sparse fast Fourier transform (SFFT) algorithms have been developed to reduce the computational complexity of Fourier transform.