A sparse discrete fourier transform using bandlimited localized modes

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(epsiv) sparse representations of the DFT discussed above. While fast versions of these algorithms relying primarily on butterfly decompositions already exist (Adams, 2006), 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 (Edelman, 1999).