A Linear Cost Algorithm to Compute the Discrete Gabor Transform

In this paper, we propose an alternative efficient method to calculate the Gabor coefficients of a signal given a synthesis window with a support of size much lesser than the length of the signal. The algorithm uses the canonical dual of the window (which does not need to be calculated beforehand) and achieves a computational cost that is linear with the signal length in both analysis and synthesis. This is done by exploiting the block structure of the matrices and using an ad hoc Cholesky decompositionof the Gabor frame matrix.