Three Distinct Algorithms for Fractional Fourier Transform

The Fractional Fourier Transform (FRFT) is a generalized form of the conventional Fourier transform, capable of representing signals at arbitrary angles in the time-frequency plane. Below are three primary discretization implementation algorithms with their characteristics and computational considerations:

Eigen-Decomposition Method This approach derives FRFT through eigen-decomposition of the Discrete Fourier Transform (DFT) matrix, expressing it as a weighted combination of DFT eigenvectors. In code implementation, this typically involves: (1) constructing the DFT matrix using fft() functions, (2) performing eigenvalue decomposition via eig() or similar linear algebra routines, (3) weighting eigenvectors by fractional powers. The key advantage is mathematical elegance and strict adherence to rotational properties; however, computational complexity scales as O(N³) with matrix operations becoming unstable for large N (>1024 points). Memory usage also increases significantly due to full matrix storage.

Chirp-Based Transformation Method Implemented through chirp multiplication and convolution operations. The algorithmic flow consists of: signal modulation with complex chirp multipliers, FFT processing, and inverse modulation - typically achieved using pointwise multiplication (.* operator) and conv() or ifft() functions. This method offers O(N log N) efficiency through FFT acceleration and is ideal for rapid prototyping with libraries like NumPy or MATLAB. Trade-offs include approximation errors from discrete chirp sampling and signal length constraints (often requiring zero-padding to power-of-two lengths for optimal FFT performance).

Sampling-Based Algorithm Direct discretization of continuous FRFT formulas using sampling and interpolation techniques. Implementation involves: (1) designing appropriate sampling grids, (2) applying interpolation kernels (e.g., spline, sinc) through interp1() or griddedInterpolant functions. While flexible for non-uniform sampling scenarios, interpolation can introduce high-frequency artifacts, making it better suited for smooth signals with limited bandwidth. Computational overhead depends on interpolation method complexity.

Algorithm Comparison: Precision: Eigen-decomposition provides optimal accuracy, while sampling methods are most vulnerable to discretization errors Speed: Chirp-based method achieves fastest computation via FFT, eigen-decomposition is slowest due to matrix operations Applicability: Chirp-based suits real-time processing, eigen-decomposition favors theoretical analysis, sampling method adapts well to irregular signal structures