|| Computing the Discrete Fourier Transform of signals with spectral frequency support
||P Charantej Reddy, V S S Prabhu Tej, Aditya Siripuram, Indian Institute of Technology Hyderabad, India; Brad Osgood, Stanford University, United States|
||D5-S6-T3: Topics in Recovery II
||Friday, 16 July, 23:40 - 00:00
||Saturday, 17 July, 00:00 - 00:20
We consider the problem of finding the Discrete Fourier Transform (DFT) of N- length signals with known frequency support of size k. When N is a power of 2 and the frequency support is a spectral set, we provide an O(k log k) algorithm to compute the DFT. Our algorithm uses some recent characterizations of spectral sets and is a generalization of the standard radix-2 algorithm.