Research Projects

The proposal focuses on the efficient computation of the Discrete Fourier Transform (DFT) using knowledge of frequency support to speed up the process. Traditional FFT algorithms leverage the recursive structure of the DFT matrix for low complexity, but when the support is known, the submatrices may not inherit these structural properties. Previous work (done by the author) suggests a connection between additive structure in frequency support and the computational complexity of DFT. The project aims to investigate this connection by 1) determining the structural conditions on the support that enable $O(k \log k)$ structured DFT algorithms, where $k$ denotes the number of non-zero DFT coefficients, 2) identifying support structures that do not allow such algorithms, 3) exploring the possibility of reducing the complexity of structured-DFT algorithms below $k \log k$, and 4) examining the robustness of structured-DFT algorithms. This work involves a mix of ideas from algorithm design, signal processing, additive combinatorics, and Fourier Analysis.