Fast algorithm of adaptive Fourier series

Adaptive Fourier decomposition (AFD, precisely 1-D AFD or Core-AFD) was originated for the goal of positive frequency representations of signals. It achieved the goal and at the same time offered fast decompositions of signals. There then arose several types of AFDs. The AFD merged with the greedy algorithm idea, and in particular, motivated the so-called pre-orthogonal greedy algorithm (pre-OGA) that was proven to be the most efficient greedy algorithm. The cost of the advantages of the AFD-type decompositions is, however, the high computational complexity due to the involvement of maximal selections of the dictionary parameters. The present paper constructs one novel method to perform the 1-D AFD algorithm. We make use of the FFT algorithm to reduce the algorithm complexity, from the original O(MN2) to O(MNN), where N denotes the number of the discretization points on the unit circle and M denotes the number of points in [0,1). This greatly enhances the applicability of AFD. Experiments are performed to show the high efficiency of the proposed algorithm.