A fast algorithm for the linear canonical transform
This work provides a fast, accurate algorithm for the LCT, which is important for applications in optics and signal processing, but the improvement over existing methods appears incremental.
The paper presents an O(N log N) algorithm for computing the linear canonical transform (LCT) using a chirp-FFT-chirp transformation based on a convergent quadrature formula for the fractional Fourier transform. The algorithm yields a unitary discrete LCT in closed form and improves the FFT for the ordinary Fourier transform case.
In recent years there has been a renewed interest in finding fast algorithms to compute accurately the linear canonical transform (LCT) of a given function. This is driven by the large number of applications of the LCT in optics and signal processing. The well-known integral transforms: Fourier, fractional Fourier, bilateral Laplace and Fresnel transforms are special cases of the LCT. In this paper we obtain an O(N*Log N) algorithm to compute the LCT by using a chirp-FFT-chirp transformation yielded by a convergent quadrature formula for the fractional Fourier transform. This formula gives a unitary discrete LCT in closed form. In the case of the fractional Fourier transform the algorithm computes this transform for arbitrary complex values inside the unitary circle and not only at the boundary. In the case of the ordinary Fourier transform the algorithm improves the output of the FFT.