FFT formulations of adaptive Fourier decomposition

Adaptive Fourier decomposition (AFD) has been found to be among the most effective greedy algorithms. AFD shows an outstanding performance in signal analysis and system identification. As compensation of effectiveness, the computation complexity is great, that is especially due to maximal selections of the parameters. In this paper, we explore the discretization of the 1-D AFD integration via with discrete Fourier transform (DFT), incorporating fast Fourier transform (FFT). We show that the new algorithm, called FFT-AFD, reduces the computational complexity from O(MN2) to O(MNlogN), the latter being the same as FFT. Through experiments, we verify the effectiveness, accuracy, and robustness of the proposed algorithm. The proposed FFT-based algorithm for AFD lays a foundation for its practical applications.