A sparse discrete fourier transform using bandlimited localized modes

Robert J. Adams, Francis X. Canning

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We have outlined a new strategy for sparse implementations of the discrete Fourier transform based on the identification of modes which generate transformed functions that are simultaneously localized and bandlimited. Numerical examples indicate that the proposed approach is more efficient than using the full DFT matrix. The examples also demonstrate that the single-level implementation reported here is notably slower than the standard FFT algorithm. The principle contributions of this paper admit multiple improvements and extensions. In particular, a multilevel organization of the spatial variable is expected to significantly reduce the computational complexities associated with the O(ε) sparse representations of the DFT discussed above. While fast versions of these algorithms relying primarily on butterfly decompositions already exist [3, 4], the framework developed herein may lead to a similarly sparse representation having a significantly different data structure. The resulting data structure may be useful in certain situations [5].

Original languageEnglish
Title of host publication2007 IEEE Antennas and Propagation Society International Symposium, AP-S
Pages41-44
Number of pages4
DOIs
StatePublished - 2007
Event2007 IEEE Antennas and Propagation Society International Symposium, AP-S - Honolulu, HI, United States
Duration: Jun 10 2007Jun 15 2007

Publication series

NameIEEE Antennas and Propagation Society, AP-S International Symposium (Digest)
ISSN (Print)1522-3965

Conference

Conference2007 IEEE Antennas and Propagation Society International Symposium, AP-S
Country/TerritoryUnited States
CityHonolulu, HI
Period6/10/076/15/07

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A sparse discrete fourier transform using bandlimited localized modes'. Together they form a unique fingerprint.

Cite this