Gabor Expansion for Discrete Periodic Samples

Overview

NOTE: Because we can easily extend a finite sequence to a periodic function, all results developed from periodic functions are automatically applicable for finite samples.

The utilization of the Gabor expansion (or the inverse sampled STFT) hinges on the availability of the dual function. Except for a few specific functions, such as Gaussian, two- and one-sided exponential at critical sampling, where the dual functions (in this case, the dual functions must be biorthogonal to each other) can be explicitly computed (see [8], [41], and [52]), analytical solutions of g(t) are not generally available. Moreover, the signals encountered in most applications today are of discrete-time. Hence, it is necessary and beneficial to extend Gabor's framework into the case of discrete-time and discrete-frequency.

The procedure of digitizing the continuous-time Gabor expansion (3.11) essentially is a standard sampling process. Thereby, we leave it for the reader to exercise. Note that sampling the time variables leads to periodicity in the frequency domain. Similarly, digitizing the frequency variable results in periodicity in the time domain. Because it digitizes both time and frequency indices, the discrete version of the Gabor expansion in general is only applied for the periodic discrete-time signals.

For discrete-time signal s[k] with period L, the discrete Gabor expansion is defined by



where the Gabor coefficients are computed by



Note that the signal s[k], synthesis function h[k], and analysis function g[k] are all periodic and have the same period L. We name (3.20) the periodic discrete Gabor expansion to distinguish it from the discrete Gabor expansion in which neither the analyzed signal nor the window functions need to be periodic. Fig. 3-6 depicts the procedure computing the periodic discrete Gabor coefficients.



Fig. 3-6 Periodic Discrete Gabor transformation

The terms DM and DN in (3.20) denote discrete time and frequency sampling steps, respectively. The oversampling rate is defined by



It is called critical sampling when a = 1 and oversampling when a > 1. For the stable reconstruction, the sampling rate must be greater or equal to one. In Wexler and Raz's original paper [185], it was required that DMM = DNN = L*. In this case, M and N are equal to the number of sampling points in time and frequency domains, respectively. The product MN is equal to the total number of the Gabor coefficients. Rewriting (3.22) obtains



which shows that the sampling rate is equal to the ratio between the total number of Gabor coefficients and the number of distinct samples. For critical sampling, the number of the Gabor coefficients is equal to the number of distinct samples. In the oversampling case, the number of the Gabor coefficients is greater than the number of samples. In this case, the resulting Gabor expansion is redundant. If we restrict DNN = L, (3.20) and (3.21) can be rewritten as



and



where N can be considered the number of frequency bins or number of frequency channels. Eq. (3.24) implies that the Gabor coefficients are periodic in n, e.g.,



Substituting L = DNN into (3.22) yields



which says that for the stable reconstruction, the time sampling step DM has to be smaller or equal to the number of frequency bins or frequency channels N.

The remaining question is how to compute g[k] for a given h[k] and sampling steps. Substituting (3.24) into the right side of (3.23) yields



Hence, the periodic discrete Gabor expansion exists if and only if the double summation is equal to the delta function, i.e.,



The double summation form is not very pleasant to work with. Eq. (3.28) does, not provide a clue to solving g[k]. By the discrete Poisson-sum formula, Eq. (3.28) can be reduced to a single summation [185], such as



where 0 £ p < DM and 0 £ q < DN. Eq. (3.29) usually is considered the discrete version of the Wexler-Raz identity.

PROOF
Expanding the left side of (3.28) obtains



Applying the discrete Poisson-sum formula (2.76) to the second summation,



which implies that (3.28) holds if and only if



Eq. (3.29) can also be formulated in terms of matrix computation, i.e.,



where H is a DMDN-by-L matrix, whose entries are defined as



m is the DMDN dimensional vector given by



Eq. (3.31) shows that the dual function g[k] is no more than the solution of a linear system. The necessary and sufficient condition of the existence of the solution of (3.31) is that m is in the range of H. At the critical sampling case, DMDN = L, H is an L-by-L square matrix. Thereby, the solution is unique if it exists. For oversampling, DMDN < L, (3.31) is an underdetermined system and thereby the solution is not unique in general. In any case, (3.31) provides a feasible way to find the discrete dual function g[k].



Fig. 3-7 h[k] = 0.425exp{-0.1(k-19)} for k ³ 19




Fig. 3-8 h[k] = 0.45exp{-0.2(k-39.5)}

Fig. 3-7 and Fig. 3-8 illustrate the one- and two-sided normalized exponential sequences and their corresponding biorthogonal functions. Based on the algorithm discussed in this section, we virtually can compute dual functions for an arbitrarily given Gabor elementary function.


_________________
* Li and Qian show [116] that the requirement DNN = L is not necessary. DN in fact can be any integer. Consequently, we could have more freedom in choosing the oversampling rate. On the other hand, however, the implementation may become complicated and less efficient. For example, we may no longer be able to use the efficient FFT algorithm to compute the Gabor expansion as well as the sampled short-time Fourier transform.

Buy the Book

Purchase Joint Time - Frequency Analysis -- Methods and Applications from Prentice Hall Professional through this link and receive the following

• Between 15% and 30% Off
• Free Shipping and Handling

Related Links:
Short-Time Fourier Transform
Gabor Expansion - Inverse Sampled STFT
Discrete Gabor Expansion

5 ratings | 3.80 out of 5

Print | PDF

Reader Comments | Submit a comment »