Overcompleteness

Overcompleteness is a concept from linear algebra that is widely used in mathematics, computer science, engineering, and statistics (usually in the form of overcomplete frames). It was introduced by R. J. Duffin and A. C. Schaeffer in 1952.
Formally, a subset of the vectors formula_1 of a Banach space formula_2, sometimes called a "system", is complete if every element in formula_2 can be approximated arbitrarily well in norm by finite linear combinations of elements in formula_1. Such a complete system is overcomplete if removal of a formula_5 from the system results in a system (i.e., formula_6) that is still complete.
In research areas such as signal processing and function approximation, overcompleteness can help researchers to achieve a more stable, more robust, or more compact decomposition than using a basis.
Relation between overcompleteness and frames.
Overcompleteness is usually discussed as a property of overcomplete frames. The theory of frame originates in a paper by Duffin and Schaeffer on non-harmonic Fourier series. The frame is defined to be a set of non-zero vectors formula_1 such that for an arbitrary formula_8,
where formula_10 denotes the inner product, formula_11 and formula_12 are positive constants called bounds of the frame. When formula_11 and formula_12 can be chosen such that formula_15, the frame is called a tight frame.
It can be seen that formula_16.
An example of frame can be given as follows.
Let each of formula_17 and formula_18 be an orthonormal basis of formula_19, then
is a frame of formula_19 with bounds formula_22.
Let formula_23 be the frame operator,
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. In this case, given formula_8, 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.
Given a tolerance formula_26 and a frame formula_27 in formula_28, for any function formula_29, define the set of all approximating functions that satisfy formula_30
Then let
formula_33 indicates the parsimony of utilizing frame formula_34 to approximate formula_35. Different formula_35 may have different formula_37 based on the hardness to be approximated with elements in the frame. The worst case to estimate a function in formula_28 is defined as
For another frame formula_40, if formula_41, then frame formula_34 is better than frame formula_40 at level formula_26. And if there exists a formula_45 that for each formula_46, we have formula_41, then formula_34 is better than formula_40 broadly.
Overcomplete frames are usually constructed in three ways.
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.
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. When the frame is finite, the decomposition can be expressed as
where formula_35 is the function one wants to approximate, formula_11 is the matrix containing all the elements in the frame, and formula_53 is the coefficients of formula_35 under the representation of formula_11. Without any other constraint, the frame will choose to give formula_53 with minimal norm in formula_28. 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 formula_53's norm in formula_59 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 formula_28 and sparsity in elements.
Examples of overcomplete frames.
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.
Gabor frames.
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 formula_61, 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 formula_61 is used in the transformation, the
information of the function in time domain are kept after the transformation.
Let operators
A Gabor frame (named after Dennis Gabor and also called Weyl-Heisenberg frame) in formula_66 is defined as the form formula_67, where formula_68 and formula_69 is a fixed function. However, not for every formula_70 and formula_71 formula_72
forms a frame on formula_66. For example, when formula_74, it is not a frame for formula_66. When formula_76, formula_72 is possible to be a frame, in which case it is a Riesz basis. So the possible situation for formula_72 being an overcomplete frame is formula_79.
The Gabor family formula_80 is also a frame and sharing the same frame bounds as formula_81
Different kinds of window function formula_61 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.
(1) formula_83, formula_72 is a frame when
formula_85
(2) formula_86, formula_72 is a frame when
formula_79
(3) formula_89, where formula_90 is the indicator function. The situation for
formula_72 to be a frame stands as follows.
1) formula_92 or formula_93, not a frame
2) formula_94 and formula_95, not a frame
3) formula_96, is a frame
4) formula_97 and is an irrational, and formula_98, is a frame
5) formula_99, formula_100 and formula_101 are relatively primes, formula_102, not a frame
6) formula_103, where formula_104 and be a natural number,
not a frame
7) formula_97, formula_94, formula_107, where formula_108 is the biggest integer not exceeding formula_109, is a frame.
The above discussion is a summary of chapter 8 in.
Wavelet frames.
A collection of wavelet usually refers to a set of functions based on formula_110
This forms an orthonormal basis for formula_66. However, when formula_113 can take values in
formula_114, the set represents an overcomplete frame and called undecimated wavelet basis. In general case, a
wavelet frame is defined as a frame for formula_66 of the form
where formula_93, formula_118, and formula_119.
The upper and lower bound of this frame can be computed as follows.
Let formula_120 be the Fourier transform for formula_121
When formula_123 are fixed, define
Then
Furthermore, when
the generated frame formula_131 is a tight frame.
The discussion in this section is based on chapter 11 in.
Applications.
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.