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).
, sometimes called a "system", is complete if every element in
can be approximated arbitrarily well in norm by finite linear combinations of elements in
[2] A system is called overcomplete if it contains more vectors than necessary to be complete, i.e., there exist
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.
[3] The theory of frames originates in a paper by Duffin and Schaeffer on non-harmonic Fourier series.
[1] A frame is defined to be a set of non-zero vectors
are positive constants called bounds of the frame.
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 or redundant.
The parsimony of the approximating functions by different frames may be considered as one way to compare their performances.
, define the set of all approximating functions that satisfy
based on the hardness to be approximated with elements in the frame.
Overcomplete frames are usually constructed in three ways.
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.
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.
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.
[7] Recently, the overcomplete Gabor frame has been combined with bayesian variable selection method to achieve both small norm expansion coefficients in
[8] In modern analysis in signal processing and other engineering field, various overcomplete frames are proposed and used.
However, the transformation only shows the frequency property of this function and loses its information in the time domain.
, 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.
[5] A collection of wavelet usually refers to a set of functions based on
, the set represents an overcomplete frame and called undecimated wavelet basis.
The upper and lower bound of this frame can be computed as follows.
The discussion in this section is based on chapter 11 in.
[5] 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.