Overcompleteness

In usual Fourier transformation, the function in time domain is transformed to the frequency domain. However, the transformation only shows the frequency property of this function and loses its information in the time domain. If a window function ${\displaystyle g}$, which only has nonzero value in a small interval, is multiplied with the original function before operating the Fourier transformation, both the information in time and frequency domains may remain at the chosen interval. When a sequence of translation of ${\displaystyle g}$ is used in the transformation, the information of the function in time domain are kept after the transformation.

Let operators

${\displaystyle T_{a}:L^{2}(R)\rightarrow L^{2}(R),(T_{a}f)(x)=f(x-a)}$

${\displaystyle E_{b}:L^{2}(R)\rightarrow L^{2}(R),(E_{b}f)(x)=e^{2\pi ibx}f(x)}$

${\displaystyle D_{c}:L^{2}(R)\rightarrow L^{2}(R),(D_{c}f)(x)={\frac {1}{\sqrt {c}}}f\left({\frac {x}{c}}\right)}$

A Gabor frame (named after Dennis Gabor and also called Weyl-Heisenberg frame) in ${\displaystyle L^{2}(R)}$ is defined as the form ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$, where ${\displaystyle a,b>0}$ and ${\displaystyle g\in L^{2}(R)}$ is a fixed function.[8] However, not for every ${\displaystyle a}$ and ${\displaystyle b}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ forms a frame on ${\displaystyle L^{2}(R)}$. For example, when ${\displaystyle ab>1}$, it is not a frame for ${\displaystyle L^{2}(R)}$. When ${\displaystyle ab=1}$, ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ is possible to be a frame, in which case it is a Riesz basis. So the possible situation for ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ being an overcomplete frame is ${\displaystyle ab<1}$. The Gabor family ${\displaystyle \{E_{mb/c}T_{nac}g_{c}\}_{m,n\in Z}}$ is also a frame and sharing the same frame bounds as ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}.}$

Different kinds of window function ${\displaystyle g}$ may be used in Gabor frame. Here examples of three window functions are shown, and the condition for the corresponding Gabor system being a frame is shown as follows.

• 
  Three window functions used in Gabor frame generation.

(1) ${\displaystyle g(x)=e^{-x^{2}}}$, ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ is a frame when ${\displaystyle ab<0.994}$

(2) ${\displaystyle g(x)={\frac {1}{cosh(\pi x)}}}$, ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ is a frame when ${\displaystyle ab<1}$

(3) ${\displaystyle g(x)=I_{[0,c)}(x)}$, where ${\displaystyle I(x)}$ is the indicator function. The situation for ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ to be a frame stands as follows.

1) ${\displaystyle a>c}$ or ${\displaystyle a>1}$, not a frame

2) ${\displaystyle c>1}$ and ${\displaystyle a=1}$, not a frame

3) ${\displaystyle a\leq c\leq 1}$, is a frame

4) ${\displaystyle a<1}$ and is an irrational, and ${\displaystyle c\in (1,2)}$, is a frame

5) ${\displaystyle a={\frac {p}{q}}<1}$, ${\displaystyle p}$ and ${\displaystyle q}$ are relatively primes, ${\displaystyle 2-{\frac {1}{q}}<c<2}$, not a frame

6) ${\displaystyle {\frac {3}{4}}<a<1}$ and ${\displaystyle c=L-1+L(1-a)}$, where ${\displaystyle L\geq 3}$ and be a natural number, not a frame

7) ${\displaystyle a<1}$, ${\displaystyle c>1}$, ${\displaystyle |c-[c]-{\frac {1}{2}}|<{\frac {1}{2}}-a}$, where ${\displaystyle [c]}$ is the biggest integer not exceeding ${\displaystyle c}$, is a frame.

The above discussion is a summary of chapter 8 in.[8]

A collection of wavelet usually refers to a set of functions based on ${\displaystyle \psi }$

${\displaystyle \{2^{\frac {j}{2}}\psi (2^{j}x-k)\}_{j,k\in Z}}$

This forms an orthonormal basis for ${\displaystyle L^{2}(R)}$. However, when ${\displaystyle j,k}$ can take values in ${\displaystyle R}$, the set represents an overcomplete frame and called undecimated wavelet basis. In general case, a wavelet frame is defined as a frame for ${\displaystyle L^{2}(R)}$ of the form

${\displaystyle \{a^{\frac {j}{2}}\psi (a^{j}x-kb)\}_{j,k\in Z}}$

where ${\displaystyle a>1}$, ${\displaystyle b>0}$, and ${\displaystyle \psi \in L^{2}(R)}$. The upper and lower bound of this frame can be computed as follows. Let ${\displaystyle {\hat {\psi }}(\gamma )}$ be the Fourier transform for ${\displaystyle \psi \in L^{1}(R)}$

${\displaystyle {\hat {\psi }}(\gamma )=\int _{R}\psi (x)e^{-2\pi ix\gamma }dx}$

When ${\displaystyle a,b}$ are fixed, define

${\displaystyle G_{0}(\gamma )=\sum _{j\in Z}|{\hat {\psi }}(a^{j}\gamma )|^{2}}$

${\displaystyle G_{1}(\gamma )=\sum _{k\neq 0}\sum _{j\in Z}|{\hat {\psi }}(a^{j}\gamma ){\hat {\psi }}(a^{j}\gamma +{\frac {k}{b}})|}$

Then

${\displaystyle B={\frac {1}{b}}\sup _{|\gamma |\in [1,a]}(G_{0}(\gamma )+G_{1}(\gamma ))<\infty }$

${\displaystyle A={\frac {1}{b}}\inf _{|\gamma |\in [1,a]}(G_{0}(\gamma )-G_{1}(\gamma ))>0}$

Furthermore, when

${\displaystyle \sum _{j\in Z}|{\hat {\psi }}(2^{j}\gamma )|^{2}=A}$

${\displaystyle \sum _{j=0}^{\infty }{\hat {\psi }}(2^{j}\gamma ){\overline {{\hat {\psi }}(2^{j}(\gamma +q))}}=0}$, for all odd integers ${\displaystyle q}$

the generated frame ${\displaystyle \{\psi _{j,k}\}_{j,k\in Z}}$ is a tight frame.

The discussion in this section is based on chapter 11 in.[8]