Overcompleteness is a concept from
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
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
R. or r. may refer to:
* ''Reign'', the period of time during which an Emperor, king, queen, etc., is ruler.
* '' Rex'', abbreviated as R., the Latin word meaning King
* ''Regina'', abbreviated as R., the Latin word meaning Queen
* or , abbreviat ...
and
A. C. Schaeffer in 1952.
[
Formally, a subset of the vectors of a Banach space , sometimes called a "system", is complete if every element in can be approximated arbitrarily well in norm by finite linear combinations of elements in .][C. Heil, A Basis Theory Primer: Expanded Edition. Boston, MA: Birkhauser, 2010.] A complete system is additionally overcomplete if there exists a which can be removed from the system while maintaining completeness (i.e., ). In this sense, the system contains more vectors than necessary to be complete, hence "''over''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.[R. Balan, P. Casazza, C. Heil, and Z. Landau, Density, overcompleteness, and localization of frames. I. theory, The Journal of Fourier Analysis and Applications, vol. 12, no. 2, 2006.]
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.[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. nline Available: https://www.jstor.org/stable/1990760] The frame is defined to be a set of non-zero vectors such that for an arbitrary ,
:
where denotes the inner product, and are positive constants called bounds of the frame. When and can be chosen such that , the frame is called a tight frame.
It can be seen that .
An example of frame can be given as follows.
Let each of and be an orthonormal basis of , then
:
is a frame of with bounds .
Let 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 , 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 and a frame in , for any function , define the set of all approximating functions that satisfy
:
Then let
:
indicates the parsimony of utilizing frame to approximate . Different may have different based on the hardness to be approximated with elements in the frame. The worst case to estimate a function in is defined as
:
For another frame , if