Fast Fourier transform using matrix decomposition

To reduce both the multiplicative complexity and total number of operations, this paper introduces a modeling scheme of the fast Fourier transform (FFT) to decompose the discrete Fourier transform (DFT) matrix recursively into a set of sparse matrices. Integrating three orthogonal transforms, the Hadamard, Modified Haar and Hybrid transforms, the proposed scheme is able to obtain different FFT representations with less computation operations than state of the arts. To investigate the applications of the proposed FFT scheme, a multi-stage image encryption algorithm is also introduced. Experimental results and security analysis are provided to show its encryption performance.