Paper ID | D5-S6-T3.1 |
Paper Title |
Computing the Discrete Fourier Transform of signals with spectral frequency support |
Authors |
P Charantej Reddy, V S S Prabhu Tej, Aditya Siripuram, Indian Institute of Technology Hyderabad, India; Brad Osgood, Stanford University, United States |
Session |
D5-S6-T3: Topics in Recovery II |
Chaired Session: |
Friday, 16 July, 23:40 - 00:00 |
Engagement Session: |
Saturday, 17 July, 00:00 - 00:20 |
Abstract |
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.
|