Computation of an eigendecomposition-based discrete fractional Fourier transform with reduced arithmetic complexity

In this paper, we introduce a method for computing an eigendecomposition-based discrete fractional Fourier transform (DFrFT) with reduced arithmetic complexity, when compared to the O(N-2) complexity of the corresponding direct computation. Our approach exploits properties of a recently introduced closed-form Hermite-Gaussian-like discrete Fourier transform eigenbasis, which is used to define the DFrFT, and includes a rounding strategy. The proposed (exact) technique requires a slightly lower number of multiplications and half or less additions than what is required by other state-of-the-art methods; if the referred rounding strategy is applied, up to 65% of multiplications can be avoided. We validate our results by means of computer experiments where the application of the transform in signal filtering and compact representation is considered. (C) 2019 Elsevier B.V. All rights reserved.