TY - GEN
T1 - A sparse discrete fourier transform using bandlimited localized modes
AU - Adams, Robert J.
AU - Canning, Francis X.
PY - 2007
Y1 - 2007
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=48349109284&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=48349109284&partnerID=8YFLogxK
U2 - 10.1109/APS.2007.4395425
DO - 10.1109/APS.2007.4395425
M3 - Conference contribution
AN - SCOPUS:48349109284
SN - 1424408776
SN - 9781424408771
T3 - IEEE Antennas and Propagation Society, AP-S International Symposium (Digest)
SP - 41
EP - 44
BT - 2007 IEEE Antennas and Propagation Society International Symposium, AP-S
T2 - 2007 IEEE Antennas and Propagation Society International Symposium, AP-S
Y2 - 10 June 2007 through 15 June 2007
ER -