Computer Sciences and Information Technology
Title : | Fast DFT Computation for Signals with Additively Structured Support |
Area of research : | Computer Sciences and Information Technology |
Focus area : | Signal Processing |
Principal Investigator : | Dr. Aditya Siripuram, Indian Institute Of Technology (IIT) Hyderabad, Telangana |
Timeline Start Year : | 2024 |
Timeline End Year : | 2027 |
Contact info : | staditya@iith.ac.in |
Details
Executive Summary : | 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. |
Total Budget (INR): | 6,60,000 |
Organizations involved