Research on Optimization Algorithms for Integer Decomposition Approximation of DFT Matrix with Sparsity Constraints

Abstract

The Discrete Fourier Transform (DFT), as an important mathematical tool in the field of communications, has been widely applied in signal processing and channel estimation. However, with the continuous growth in antenna arrays, the number of channels, and communication bandwidth, the computational resources required to implement the FFT on a chip have been increasing significantly. Therefore, there is a need for more efficient and simplified methods to implement the DFT, aiming to reduce computational complexity and resource consumption without compromising accuracy. To address this issue, this paper adopts an approximation approach for the DFT, which approximates the DFT matrix as a product of a series of sparse matrices with limited element values. Based on this approach, this paper proposes an integer matrix decomposition approximation algorithm with sparsity constraints, aimed at reducing the computational complexity of the DFT and optimizing the computational process. Numerical experiments demonstrate that, compared to the traditional FFT algorithm, the proposed method reduces computational complexity by approximately fivefold, highlighting its significant advantages and practical engineering value.