You Gao

You Gao, Tao Qian, Vladimir Temlyakov et al.

As a new type of series expansion, the so-called one-dimensional adaptive Fourier decomposition (AFD) and its variations (1D-AFDs) have effective applications in signal analysis and system identification. The 1D-AFDs have considerable influence to the rational approximation of one complex variable and phase retrieving problems, etc. In a recent paper, Qian developed 2D-AFDs for treating square images as the essential boundary of the 2-torus embedded into the space of two complex variables. This paper studies the numerical aspects of multi-dimensional AFDs, and in particular 2D-AFDs, which mainly include (i) Numerical algorithms of several types of 2D-AFDs in relation to image representation; (ii) Perform experiments for the algorithms with comparisons between 5 types of image reconstruction methods in the Fourier category; and (iii) New and sharper estimations for convergence rates of orthogonal greedy algorithm and pre-orthogonal greedy algorithm. The comparison shows that the 2D-AFD methods achieve optimal results among the others.

You Gao, Min Ku, Tao Qian

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. 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 offers one formulation of the 1-D AFD algorithm by building the FFT algorithm into it. Accordingly, the algorithm complexity is reduced, from the original $\mathcal{O}(M N^2)$ to $\mathcal{O}(M N\log_2 N)$, 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 carried out to show the high efficiency of the proposed algorithm.