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 { ϕ i } i ∈ J {\displaystyle \{\phi _{i}\}_{i\in J}} of a Banach space X {\displaystyle X} , sometimes called a "system", is complete if every element in X {\displaystyle X} can be approximated arbitrarily well in norm by finite linear combinations of elements in { ϕ i } i ∈ J {\displaystyle \{\phi _{i}\}_{i\in J}} . A system is called overcomplete if it contains more vectors than necessary to be complete, i.e., there exist ϕ j ∈ { ϕ i } i ∈ J {\displaystyle \phi _{j}\in \{\phi _{i}\}_{i\in J}} that can be removed from the system such that { ϕ i } i ∈ J ∖ { ϕ j } {\displaystyle \{\phi _{i}\}_{i\in J}\setminus \{\phi _{j}\}} remains 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 The theory of frames originates in a paper by Duffin and Schaeffer on non-harmonic Fourier series. A frame is defined to be a set of non-zero vectors { ϕ i } i ∈ J {\displaystyle \{\phi _{i}\}_{i\in J}} such that for an arbitrary f ∈ H {\displaystyle f\in {\mathcal {H}}} ,
A ‖ f ‖ 2 ≤ ∑ i ∈ J | ⟨ f , ϕ i ⟩ | 2 ≤ B ‖ f ‖ 2 {\displaystyle A\|f\|^{2}\leq \sum _{i\in J}|\langle f,\phi _{i}\rangle |^{2}\leq B\|f\|^{2}}
where ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } denotes the inner product, A {\displaystyle A} and B {\displaystyle B} are positive constants called bounds of the frame. When A {\displaystyle A} and B {\displaystyle B} can be chosen such that A = B {\displaystyle A=B} , the frame is called a tight frame. It can be seen that H = span { ϕ i } {\displaystyle {\mathcal {H}}=\operatorname {span} \{\phi _{i}\}} . An example of frame can be given as follows. Let each of { α i } i = 1 ∞ {\displaystyle \{\alpha _{i}\}_{i=1}^{\infty }} and { β i } i = 1 ∞ {\displaystyle \{\beta _{i}\}_{i=1}^{\infty }} be an orthonormal basis of H {\displaystyle {\mathcal {H}}} , then
{ ϕ i } i = 1 ∞ = { α i } i = 1 ∞ ∪ { β i } i = 1 ∞ {\displaystyle \{\phi _{i}\}_{i=1}^{\infty }=\{\alpha _{i}\}_{i=1}^{\infty }\cup \{\beta _{i}\}_{i=1}^{\infty }}
is a frame of H {\displaystyle {\mathcal {H}}} with bounds A = B = 2 {\displaystyle A=B=2} . Let S {\displaystyle S} be the frame operator,
… excerpt ends here. Continue reading the full article.
