Efficient calculation of finite Gabor transforms

The Gabor transform may be viewed as a collection of localized Fourier transforms and as such is useful for analysis of nonstationary signals and images. We present a new approach to analyzing the Gabor transform and use it to study the various critically sampled discretizations that form the infinite-discrete, periodic finite-discrete, and nonperiodic finite-discrete versions of the transform. In particular, we distinguish between the analysis and synthesis forms of the transform, and introduce an intermediate operation that decomposes both forms into collections of independent Toeplitz operators. In the continuous, the infinite-discrete, and the periodic finite-discrete cases, this decomposition allows us to show that, for appropriate windows, the analysis and synthesis transforms are inverses of each other. In the nonperiodic finite-discrete case this relation no longer holds, but we are still able to use the decomposition and results on Toeplitz matrices to show that both the transform and the inverse transform of P discrete samples are computable in O(P log P) operations (after a setup cost of O(Plog²P)). Furthermore, we use the decomposition to study in detail the differences between the periodic and nonperiodic versions of the transform and to compare their conditioning