overcompleteness

The theory of frames originates in a paper by Duffin and Schaeffer on non-harmonic Fourier series.R. J. Duffin and A. C. Schaeffer, A class of nonharmonic Fourier series, Transactions of the American Mathematical Society, vol. 72, no. 2, pp. 341{366, 1952. [Online]. Available: https://www.jstor.org/stable/1990760 A frame is defined to be a set of non-zero vectors $\backslash \{\backslash phi\_i\backslash \}\_\{i\backslash in\; J\}$ such that for an arbitrary $f\backslash in\backslash mathcal\{H\}$,

: $A\backslash |f\backslash |^2\backslash leq\backslash sum\_\{i\backslash in\; J\}|\backslash langle\; f,\; \backslash phi\_i\; \backslash rangle|^2\backslash leq\; B\backslash |f\backslash |^2$

where $\backslash langle\backslash cdot,\backslash cdot\backslash rangle$ denotes the inner product, $A$ and $B$ are positive constants called bounds of the frame. When $A$ and $B$ can be chosen such that $A=B$, the frame is called a tight frame.K. Grochenig, Foundations of time-frequency analysis. Boston, MA: Birkhauser, 2000.

It can be seen that $\backslash mathcal\{H\}=\backslash operatorname\{span\}\backslash \{\backslash phi\_i\backslash \}$.

An example of frame can be given as follows.

Let each of $\backslash \{\backslash alpha\_i\backslash \}\_\{i=1\}^\{\backslash infty\}$ and $\backslash \{\backslash beta\_i\backslash \}\_\{i=1\}^\{\backslash infty\}$ be an orthonormal basis of $\backslash mathcal\{H\}$, then

: $\backslash \{\backslash phi\_i\backslash \}\_\{i=1\}^\{\backslash infty\}=\backslash \{\backslash alpha\_i\backslash \}\_\{i=1\}^\{\backslash infty\}\backslash cup\backslash \{\backslash beta\_i\backslash \}\_\{i=1\}^\{\backslash infty\}$

is a frame of $\backslash mathcal\{H\}$ with bounds $A=B=2$.

Let $S$ be the frame operator,

: $Sf=\backslash sum\_\{i\backslash in\; J\}\backslash langle\; f,\; \backslash phi\_i\; \backslash rangle\backslash phi\_i$

A frame that is not a Riesz basis, in which case it consists of a set of functions more than a basis, is said to be overcomplete or redundant.O. Christensen, An Introduction to Frames and Riesz Bases. Boston, MA: Birkhauser, 2003. In this case, given $f\backslash in\backslash mathcal\{H\}$, it can have different decompositions based on the frame. The frame given in the example above is an overcomplete frame.

When frames are used for function estimation, one may want to compare the performance of different frames. The parsimony of the approximating functions by different frames may be considered as one way to compare their performances.[http://www.stat.duke.edu/~banks/218-lectures.dir/dmlect7.pdf], STA218, Data Mining Class Note at Duke University

Given a tolerance $\backslash epsilon$ and a frame $F=\backslash \{\backslash phi\_i\backslash \}\_\{i\backslash in\; J\}$ in $L^2(\backslash mathbb\{R\})$, for any function $f\backslash in\; L^2(\backslash mathbb\{R\})$, define the set of all approximating functions that satisfy

:

Then let

: $k\_\{F\}(f,\backslash epsilon)=\backslash inf\backslash \{k:\; \backslash hat\{f\}\backslash in\; N(f,\backslash epsilon)\backslash \}$

$k(f,\backslash epsilon)$ indicates the parsimony of utilizing frame $F$ to approximate $f$. Different $f$ may have different $k$ based on the hardness to be approximated with elements in the frame. The worst case to estimate a function in $L^2(\backslash mathbb\{R\})$ is defined as

: $k\_F\; (\backslash epsilon)=\backslash sup\_\{f\backslash in\; L^2(\backslash mathbb\{R\})\}\backslash \{k\_\{F\}(f,\backslash epsilon)\backslash \}$

For another frame $G$, if

Overcomplete frames are usually constructed in three ways.

1. Combine a set of bases, such as wavelet basis and Fourier basis, to obtain an overcomplete frame.
2. Enlarge the range of parameters in some frame, such as in Gabor frame and wavelet frame, to have an overcomplete frame.
3. Add some other functions to an existing complete basis to achieve an overcomplete frame.

An example of an overcomplete frame is shown below. The collected data is in a two-dimensional space, and in this case a basis with two elements should be able to explain all the data. However, when noise is included in the data, a basis may not be able to express the properties of the data. If an overcomplete frame with four elements corresponding to the four axes in the figure is used to express the data, each point would be able to have a good expression by the overcomplete frame.

Image:OvercompleteframeGuoxian.jpg|An example of an overcomplete frame

The flexibility of the overcomplete frame is one of its key advantages when used in expressing a signal or approximating a function. However, because of this redundancy, a function can have multiple expressions under an overcomplete frame.M. S. Lewicki and T. J. Sejnowski, Learning overcomplete representations, Neural Computation, vol. 12, no. 2, pp. 337{365, 2000. When the frame is finite, the decomposition can be expressed as

: $f=Ax$

where $f$ is the function one wants to approximate, $A$ is the matrix containing all the elements in the frame, and $x$ is the coefficients of $f$ under the representation of $A$. Without any other constraint, the frame will choose to give $x$ with minimal norm in $L^2(\backslash mathbb\{R\})$. Based on this, some other properties may also be considered when solving the equation, such as sparsity. So different researchers have been working on solving this equation by adding other constraints in the objective function. For example, a constraint minimizing $x$'s norm in $L^1(\backslash mathbb\{R\})$ may be used in solving this equation. This should be equivalent to the Lasso regression in statistics community. Bayesian approach is also used to eliminate the redundancy in an overcomplete frame. Lweicki and Sejnowski proposed an algorithm for overcomplete frame by viewing it as a probabilistic model of the observed data. Recently, the overcomplete Gabor frame has been combined with bayesian variable selection method to achieve both small norm expansion coefficients in $L^2(\backslash mathbb\{R\})$ and sparsity in elements.P. Wolfe, S. Godsill, and W. Ng, Bayesian variable selection and regularization for time-frequency surface estimation, J. R. Statist. Soc. B, vol. 66, no. 3, 2004.

In modern analysis in signal processing and other engineering field, various overcomplete frames are proposed and used. Here two common used frames, Gabor frames and wavelet frames, are introduced and discussed.

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 $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 $g$ is used in the transformation, the

information of the function in time domain are kept after the transformation.

Let operators

: $T\_a:\; L^2(R)\backslash rightarrow\; L^2(R),\; (T\_af)(x)=f(x-a)$

: $E\_b:\; L^2(R)\backslash rightarrow\; L^2(R),\; (E\_bf)(x)=e^\{2\backslash pi\; ibx\}f(x)$

: $D\_c:\; L^2(R)\backslash rightarrow\; L^2(R),\; (D\_cf)(x)=\backslash frac\{1\}\{\backslash sqrt\; c\}f\backslash left(\backslash frac\{x\}\{c\}\backslash right)$

A Gabor frame (named after Dennis Gabor and also called Weyl-Heisenberg frame) in $L^2(R)$ is defined as the form $\backslash \{E\_\{mb\}T\_$

{na}g\}_{m,n\in Z}, where $a,b>0$ and $g\backslash in\; L^2(R)$ is a fixed function.O. Christensen, An Introduction to Frames and Riesz Bases. Boston, MA: Birkhauser, 2003. However, not for every $a$ and $b$ $\backslash \{E\_\{mb\}T\_\{na\}g\backslash \}\_\{m,n\backslash in\; Z\}$

forms a frame on $L^2(R)$. For example, when $ab>1$, it is not a frame for $L^2(R)$. When $ab=1$, $\backslash \{E\_\{mb\}T\_\{na\}g\backslash \}\_\{m,n\backslash in\; Z\}$ is possible to be a frame, in which case it is a Riesz basis. So the possible situation for $\backslash \{E\_\{mb\}T\_\{na\}g\backslash \}\_\{m,n\backslash in\; Z\}$ being an overcomplete frame is .

The Gabor family $\backslash \{E\_\{mb/c\}T\_\{nac\}g\_c\backslash \}\_\{m,n\backslash in\; Z\}$ is also a frame and sharing the same frame bounds as $\backslash \{E\_\{mb\}T\_\{na\}g\backslash \}\_\{m,n\backslash in\; Z\}.$

Different kinds of window function $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.

Image:WindowfunctionsGuoxian.jpg|Three window functions used in Gabor frame generation.

(1) $g(x)=e^\{-x^2\}$, $\backslash \{E\_\{mb\}T\_\{na\}g\backslash \}\_\{m,n\backslash in\; Z\}$ is a frame when

(2) $g(x)=\backslash frac\{1\}\{cosh(\backslash pi\; x)\}$, $\backslash \{E\_\{mb\}T\_\{na\}g\backslash \}\_\{m,n\backslash in\; Z\}$ is a frame when

(3) $g(x)=I\_\{[0,c)\}(x)$, where $I(x)$ is the indicator function. The situation for

$\backslash \{E\_\{mb\}T\_\{na\}g\backslash \}\_\{m,n\backslash in\; Z\}$ to be a frame stands as follows.

1) $a>c$ or $a>1$, not a frame

2) $c>1$ and $a=1$, not a frame

3) $a\backslash leq\; c\backslash leq1$, is a frame

4) and is an irrational, and $c\backslash in(1,2)$, is a frame

5) , $p$ and $q$ are relatively primes, $2-\backslash frac\{1\}\{q\}$

, not a frame

6)

not a frame

7) , $c>1$, , where $[c]$ is the biggest integer not exceeding $c$, is a frame.

The above discussion is a summary of chapter 8 in.

A collection of wavelet usually refers to a set of functions based on $\backslash psi$

: $\backslash \{2^\backslash frac\{j\}\{2\}\backslash psi(2^jx-k)\backslash \}\_\{j,k\backslash in\; Z\}$

This forms an orthonormal basis for $L^2(R)$. However, when $j,k$ can take values in

$R$, the set represents an overcomplete frame and called undecimated wavelet basis. In general case, a

wavelet frame is defined as a frame for $L^2(R)$ of the form

: $\backslash \{a^\backslash frac\{j\}\{2\}\backslash psi(a^jx-kb)\backslash \}\_\{j,k\backslash in\; Z\}$

where $a>1$, $b>0$, and $\backslash psi\backslash in\; L^2(R)$.

The upper and lower bound of this frame can be computed as follows.

Let $\backslash hat\{\backslash psi\}(\backslash gamma)$ be the Fourier transform for $\backslash psi\backslash in\; L^1(R)$

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

When $a,b$ are fixed, define

: $G\_0(\backslash gamma)=\backslash sum\_\{j\backslash in\; Z\}\; |\backslash hat\{\backslash psi\}(a^j\backslash gamma)|^2$

: $G\_1(\backslash gamma)=\backslash sum\_\{k\backslash neq0\}\backslash sum\_\{j\backslash in\; Z\}\; |\backslash hat\{\backslash psi\}(a^j\backslash gamma)\backslash hat\{\backslash psi\}(a^j\backslash gamma+\backslash frac\{k\}\{b\})|$

Then

:

: $A=\backslash frac\{1\}\{b\}\backslash inf\_\{|\backslash gamma|\backslash in[1,a]\}(G\_0(\backslash gamma)-G\_1(\backslash gamma))>0$

Furthermore, when

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

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

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

The discussion in this section is based on chapter 11 in.

Overcomplete Gabor frames and Wavelet frames have been used in various research area including signal detection, image representation, object recognition, noise reduction, sampling theory, operator theory, harmonic analysis, nonlinear sparse approximation, pseudodifferential operators, wireless communications, geophysics, quantum computing, and filter banks.

{{Reflist}}

Category:Linear algebra

Category:Mathematical analysis