Gabor Expansion - Inverse Sampled STFT

Overview

Instead of representing a signal either as the function of time or the function of frequency separately, in 1946, Gabor suggested representing a signal in two dimensions, with time and frequency as coordinates [53]. Gabor named such two-dimensional representations the "information diagrams as areas in them are proportional to the number of independent data which they can convey. Gabor pointed out that there are certain "elementary signals" which occupy the smallest possible area in the information diagram. Each elementary signal can be considered as conveying exactly one datum, or one "quantum of information." Any signal can be expanded in terms of these by a process which includes time analysis and frequency analysis as extreme cases. For signal s(t), the Gabor expansion is defined as



where T and W denote the time and frequency sampling steps. Fig. 3-4 illustrates the Gabor sampling grid.



Fig. 3-4 Gabor sampling lattice

In Gabor's original paper, he selected the Gaussian function as the elementary function, i.e.,



because the Gaussian function is optimally concentrated in the joint time-frequency domain according to the uncertainty principle, that is,



which is the lower bound of the uncertainty inequality.

Although Gabor restricted himself to an elementary signal that has a Gaussian shape, his signal expansion in fact holds for rather arbitrarily shaped signals. For almost any signal h(t), its time-shifted and harmonically modulated version can be used as the Gabor elementary functions. The necessary condition of the existence of the Gabor expansion is that the sampling cell TW must be small enough to satisfy



Intuitively, if the sampling cell TW is too large, we may not have enough information to completely recover the original signal. On the other hand, if the sampling cell TW. is too small, the representation will be redundant. Traditionally, it is called critical sampling when TW = 2p and oversampling when TW < 2p. It is interesting to note that although Gabor was not known to have investigated the existence of the formula (3.11), the sampling cell that he selected, TW = 2p, happened to be the most compact representation!

Gabor was also not known to have published any practical algorithms of computing the Gabor coefficients*. Despite the earlier treatment by Auslander et al [3], Gabor's work was not very popular until 1980, in particular, after Bastiaans related the Gabor expansion and short-time Fourier transform (see [8], [9], and [10]). Bastiaans introduced the sampled short-time Fourier transform to compute the Gabor coefficients.

[*In his notable paper, Gabor proposed an iteration approach to compute the coefficients C_m,n which, however, has been found not to converge in general [54]. ]

As mentioned in the preceding section, the continuous-time inverse STFT is a highly redundant expansion. In applications, for a compact presentation we usually use sampled STFT. However, the imprudent choice of analysis function g(t) and sampling steps, T and W, may lead to the sampled STFT being non-invertible. With the help of the Gabor expansion, we now can easily solve the problem of the inverse of sampled STFT, even though it was apparently not Gabor's original motivation.

Based upon the expansion theorem introduced in Chapter 2, if the set of the Gabor elementary functions {h_m,n(t)} is complete, then there will be a dual function (or auxiliary function) g(t) such that the Gabor coefficients can be computed by the regular inner product operation, i.e.,



which is the sampled STFT and also known as the Gabor transform. It can be shown that for critical sampling, the Gabor elementary functions {h_m,n(t)} are linearly independent. In this case, the dual function is unique and biorthogonal to h(t). At oversampling, the selection of the auxiliary function is not unique. There are two fundamental problems regarding the implementation of the Gabor expansion:

• how to compute the dual functions g(t)?
• how to select the dual function g(t) if they are not unique?

Substituting (3.14) into the right side of (3.11) yields



Obviously, the Gabor expansion exists if and only if the double summation is a delta function, that is,



By the Poisson-sum formula, (3.16) can be reduced to a single integration [185], i.e.,



where



where T₀ =2p/W and W₀ = 2p/T. In some literature, (3.17) is named the Wexler-Raz identity, which plays an important role in computing the dual functions. Note that except for the critical sampling, TW=2p, g_m,n (t)¹g⁰_m,n (t).


Fig. 3-5 Although the Gabor elementary function (dotted line) is optimally concentrated in the joint time-frequency domain, the corresponding biorthogonal function (solid line) is neither localized in time nor in frequency.

At critical sampling, the set of {h_m,n(t)} is linearly independent. In this case, we say g(t) and h(t) are biorthogonal to each other. For oversampling, the set of {h_m,n(t)} is linearly dependent. The resulting presentation is redundant. Bastiaans gave the closed form of the solution g(t) for the Gaussian function h(t) at critical sampling. The results are plotted in Fig. 3-5. Note that, although h(t) (dotted line) is optimally concentrated in the joint time-frequency domain, the corresponding biorthogonal function g(t) (solid line) is neither concentrated in time nor in frequency.

It is worth noting that, unlike harmonically related complex sinusoidal functions used in the Fourier series, which are orthonormal, the set of the Gabor elementary functions in general does not constitute an orthogonal basis. In this case, the dual function g(t) is not equal to the Gabor elementary function h(t). The direct consequence is that although we could easily have the Gabor elementary functions optimally concentrated in the joint time-frequencies domain, the dual function g(t) may not be localized. Consequently, the Gabor coefficients C_m,n the inner product of signal and dual functions, do not necessarily reflect the signal's behavior in the vicinity of [mT-D_t, mT+D_t] x [nW-D_w, nW+D_w]. Whether or not the Gabor coefficients C_m,n describe the signal's local behavior depends on the property of the dual function. If g(t) is badly concentrated in the joint time-frequency domain, the Gabor coefficients C_m,n will fail to describe the signal's local behavior. We shall discuss a great deal of the selection of dual functions in Section 3.5.
Finally, we should emphasize that the dual functions g(t) and h(t) are exchangeable. The Gabor expansion can be written in either way as



Which one, g(t) or h(t), is used for the analysis function to compute the Gabor coefficients depends on the applications at hand. If we are mainly interested in Gabor coefficients, then we may use h_m,n(t) to calculate C_m,n because it is selected first and thereby easier to make it meet our requirements. In this case, once h(t) is properly selected, the Gabor coefficients C_m,n will well describe the signal's local time and frequency behaviors.

_______________________

* Dennis Gabor was born on June 5, 1900, in Budapest, Hungary. His talent for memorization — an asset in any academic field — appeared at the age of twelve, when he earned a prize from his father for learning by heart, in German, a 430-line poem. Gabor finished his doctorate in electrical engineering in 1927. His work in communication theory and holography started at the end of World War II. It was during that time that he wrote the famous Gabor expansion paper. In 1949, he joined the Imperial College of Science and Technology at London University and in the late sixties became a staff scientist at CBS Laboratories in the United States. While his formal education had been largely in the applied engineering fields, he had not neglected to study the basic physical and mathematical tools that would facilitate his life's work, which was mostly motivated by a desire to create or perfect a particular device invariably secured on a sound mathematical footing. His genius as an inventor lay in an innate ability to focus on a final goal, regardless of the difficulties. His endeavor paid off. In 1971, the Royal Swedish Academy of Sciences presented Dennis Gabor with the Nobel Prize for his discovery of the principles underlying the science of holography.

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 for Discrete Periodic Samples
Discrete Gabor Expansion

8 ratings | 4.12 out of 5

Print | PDF

Reader Comments | Submit a comment »