Computational Schemes for Warped DFT and Its Inverse

Unlike discrete Fourier transform (DFT), warped DFT (WDFT) obtains nonuniformly spaced frequency samples based on an all-pass warping. WDFT finds applications in diverse fields, the most notable being audio processing. An explicit structure for the realization of WDFT and its generalized form, the overcomplete WDFT, is proposed in this work which leads to savings in the computational requirements for both WDFT and inverse WDFT (IWDFT). This structure exploits the symmetry of the Q matrix to reduce the operations involved at that stage to about half. Further, the computation of IWDFT is known to be problematic since the matrix is ill-conditioned. In this work, an iterative scheme is proposed to compute this inverse. While the computational error of the iterative inverse is shown to be comparable to the best existing scheme based on the overcomplete WDFT, the iterative inverse does not need the additional transform coeffcients of the overcomplete WDFT.