### Critical sampling, oversampling, and the Balian-Low Theorem

We have mentioned earlier that Gabor suggested to use the Gaussian function as atom , since it minimizes the uncertainty principle inequality. Recalling that the are the coherent states associated to the Weyl-Heisenberg group in quantum mechanics, we remind that this choice corresponds to the canonical coherent states.

Exploiting the link between Gaussian coherent states and the Bargmann space of entire functions it was proved in 1971 by Peremolov [Per71] and independently by Bargmann et al. [BBGK71] that the canonical coherent states are complete in if and only if . Bacry, Grossmann and Zak [BGZ75] showed in 1975 that if , then

 (12)

although the are complete in . Formula (0.10) implies that for Gabor's original choice of the Gaussian and , the set is not a frame for . Thus there is no numerically stable algorithm to reconstruct from the .

Bastiaans was the first who has published an analytic solution to compute the Gabor expansion coefficients for the case and equal the Gaussian. He constructed a function , such that

 (13)

with . Note however that (0.11) does not even converge in a weak -sense, in fact is not in , as was pointed out by Janssen [Jan81]. He showed that convergence holds only in the sense of distributions.

Using entire function methods, Lyubarskii and independently Seip and Wallsten showed that for the Gaussian the family is a frame whenever . According to Janssen the dual function is then even a Schwartz function.

As a corollary of deep results on -algebras by Rieffel it was proved that the set is incomplete in for any , if . This fact can be seen as a Nyquist criterion for Gabor systems. The non-constructive proof makes use of the properties of the von Neumann algebras, generated by the operators . Daubechies [Dau90] derived this result for the special case of rational . Janssen showed that the cannot establish a frame for any , if without any restriction on . One year earlier Landau proved the weaker result that cannot be a frame for if and both and satisfy certain decay conditions [Lan93]. On the other hand his result includes the case of irregular Gabor systems, where the sampling set is not necessarily a lattice in .

All these results remind on the role of the Nyquist density for sampling and reconstruction of bandlimited functions in Shannon's Sampling Theorem. Hence it is natural to classify Gabor systems according to the corresponding sampling density of the time-frequency lattice:

• oversampling - : Frames with excellent time-frequency localization properties exist (a particular example are frames with Gaussian and appropriate oversampling rate).
• critical sampling - : Frames and orthonormal bases are possible, but - as we will see below - without good time-frequency localization;
• undersampling - : In this case any Gabor family will be incomplete, in the sense that the closed linear span is a proper subspace of , in particular one cannot have a frame for .

The case is also distinguished among all others by the fact, that the time-frequency shift operators, which are used to build the coherent frame, commute with each other (without non-trivial factor).

Clearly there exist many choices for , so that is a frame or even an orthonormal basis (ONB) for . Two well-known examples of functions for which the family constitutes an ONB are the rectangle function (which is 1 for and zero else), and the sinc-function . However in the first case , in the second case . Thus these choices lead to systems with bad localization properties in either time or frequency. Even if we drop the orthogonality requirement, we cannot construct Riesz bases with good time-frequency localization properties for the limit case . This is the contents of the celebrated Balian-Low Theorem [Bal81,Low85], which describes one of the key facts in Gabor analysis:

Balian-Low Theorem: If the constitute a Riesz basis for , then

According to Gabor's heuristics the integer lattice in the time-frequency plane was chosen to make the choice of coefficients as unique as possible'' (unfortunately one cannot have strict uniqueness since there are bounded sequences which represent the zero-function in a non-trivial, but only distributional way). In focusing his attention on this uniqueness problem he apparently overlooked that the use of well-localized building blocks to obtain an expansion does not imply that the computation of the coefficient can be carried out by a local'' procedure, using only information localized around the point in the time-frequency plane. The problem of lack of time-frequency locality of the Gabor coefficients is not only severe in the critical case, but becomes more and more serious as one uses a sequence of lattices which are close-to-critical sampling. This fact becomes clear by observing that the corresponding dual functions lose their time-frequency localization, see also Figure 5.

It appears that Gabor families having some (modest) redundancy, which allows to have a pair of dual Gabor atoms where each function of this dual pair is well localized in time and frequency (cf. also Figure 5), are more appropriate as a tool in Gabor's original sense. Clearly under such premises one has to give up the uniqueness of coefficients and even the uniqueness of . The choice is in some sense canonical and - as we have seen above - appropriate Gabor coefficients can be easily determined as samples of the STFT with window .

Is there no way to obtain an orthonormal basis for with good time-frequency properties based on Gabor's approach?

Wilson observed that for the study of the kinetic operator in quantum mechanics, one does not need basis functions that distinguish between positive and negative frequencies of the same order. Musicians probably would also agree to such a relaxation of requirements. Thus we are looking for complete orthonormal systems which are essential of Weyl-Heisenberg type, but allowing to have linear combinations of with . It turns out that by this seemingly small modification a family of orthonormal bases for can be constructed, the so-called Wilson bases, avoiding the Balian-Low phenomenon. Wilson's suggestion was turned into a construction by Daubechies, Jaffard and Journé, who gave a recipe how to obtain such an orthonormal Wilson basis from a tight Gabor frame for and .

A general construction that includes many examples of Wilson bases as well as wavelet bases are the local trigonometric bases of Coifman and Meyer.