A set Ψ={ψi}i∈IΨ={ψi}i∈I is called a basis for a finite-dimensional vector space VV if the vectors in the set span VV and are linearly independent. This implies that each vector in the space can be represented as a linear combination of this (smaller, except in the trivial case) set of basis vectors in a unique fashion. Furthermore, the coefficients of this linear combination can be found by the inner product of the signal and a dual set of vectors. In discrete settings, we will only consider real finite-dimensional Hilbert spaces where V=RNV=RN and I={1,...,N}I={1,...,N}.
Mathematically, any signal x∈RNx∈RN may be expressed as,
x
=
∑
i
∈
I
a
i
ψ
i
˜
,
x
=
∑
i
∈
I
a
i
ψ
i
˜
,
(1)where our coefficients are computed as ai=〈x,ψi〉ai=〈x,ψi〉 and {ψi˜}i∈I{ψi˜}i∈I are the vectors that constitute our dual basis. Another way to denote our basis and its dual is by how they operate on xx. Here, we call our dual basis Ψ˜Ψ˜ our synthesis basis (used to reconstruct our signal by Equation 1) and ΨΨ is our analysis basis.
An orthonormal basis (ONB) is defined as a set of vectors Ψ={ψi}i∈IΨ={ψi}i∈I that form a basis and whose elements are orthogonal and unit norm. In other words, 〈ψi,ψj〉=0〈ψi,ψj〉=0 if i≠ji≠j and one otherwise. In the case of an ONB, the synthesis basis is simply the Hermitian adjoint of analysis basis (Ψ˜=ΨTΨ˜=ΨT).
It is often useful to generalize the concept of a basis to allow for sets of possibly linearly dependent vectors, resulting in what is known as a frame. More formally, a frame is a set of vectors {Ψi}i=1n{Ψi}i=1n in RdRd, d<nd<n corresponding to a matrix Ψ∈Rd×nΨ∈Rd×n, such that for all vectors x∈Rdx∈Rd,
A
x
2
2
≤
Ψ
T
x
2
2
≤
B
x
2
2
A
x
2
2
≤
Ψ
T
x
2
2
≤
B
x
2
2
(2)with 0<A≤B<∞0<A≤B<∞. Note that the condition A>0A>0 implies that the rows of ΨΨ must be linearly independent. When AA is chosen as the largest possible value and BB as the smallest for these inequalities to hold, then we call them the (optimal) frame bounds. If AA and BB can be chosen as A=BA=B, then the frame is called AA-tight, and if A=B=1A=B=1, then ΨΨ is a Parseval frame. A frame is called equal-norm, if there exists some λ>0λ>0 such that Ψi2=λΨi2=λ for all i=1,...,Ni=1,...,N, and it is unit-norm if λ=1λ=1. Note also that while the concept of a frame is very general and can be defined in infinite-dimensional spaces, in the case where ΨΨ is a d×Nd×N matrix AA and BB simply correspond to the smallest and largest eigenvalues of ΨΨTΨΨT, respectively.
Frames can provide richer representations of data due to their redundancy: for a given signal xx, there exist infinitely many coefficient vectors αα such that x=Ψαx=Ψα. In particular, each
choice of a dual frame Ψ˜Ψ˜ provides a different choice of
a coefficient vector αα. More formally, any frame satisfying
Ψ
Ψ
˜
T
=
Ψ
˜
Ψ
T
=
I
Ψ
Ψ
˜
T
=
Ψ
˜
Ψ
T
=
I
(3)is called an (alternate) dual frame. The particular choice Ψ˜=(ΨΨT)-1ΨΨ˜=(ΨΨT)-1Ψ is referred to as the canonical dual frame. It is also known as the Moore-Penrose pseudoinverse. Note that since A>0A>0 requires ΨΨ to have linearly independent rows, we ensure that ΨΨTΨΨT is invertible, so that Ψ˜Ψ˜ is well-defined. Thus, one way to obtain a set of feasible coefficients is via
α
d
=
Ψ
T
(
Ψ
Ψ
T
)
-
1
x
.
α
d
=
Ψ
T
(
Ψ
Ψ
T
)
-
1
x
.
(4)One can show that this sequence is the smallest coefficient sequence in ℓ2ℓ2 norm, i.e., αd2≤α2αd2≤α2 for all αα such that x=Ψαx=Ψα.
Finally, note that in the sparse approximation literature, it is also common for a basis or frame to be referred to as a dictionary or overcomplete dictionary respectively, with the dictionary elements being called atoms.
