Frame (linear algebra)

In linear algebra, a frame of an inner product space is a generalization of a basis of a vector space to sets that may be linearly dependent. In the terminology of signal processing, a frame provides a redundant, stable way of representing a signal. Frames are used in error detection and correction and the design and analysis of filter banks and more generally in applied mathematics, computer science, and engineering.
Definition and motivation.
Motivating example: computing a basis from a linearly dependent set.
Suppose we have a set of vectors formula_1 in the vector space "V" and we want to express an arbitrary element formula_2 as a linear combination of the vectors formula_3, that is, we want to find coefficients formula_4 such that
If the set formula_6 does not span formula_7, then such coefficients do not exist for every such formula_8. If formula_6 spans formula_7 and also is linearly independent, this set forms a basis of formula_7, and the coefficients formula_12 are uniquely determined by formula_8. If, however, formula_3 spans formula_7 but is not linearly independent, the question of how to determine the coefficients becomes less apparent, in particular if formula_7 is of infinite dimension.
Given that formula_1 spans formula_7 and is linearly dependent, one strategy is to remove vectors from the set until it becomes linearly independent and forms a basis. There are some problems with this plan:
Formal definition.
Let "V" be an inner product space and formula_27 be a set of vectors in formula_7. These vectors satisfy the "frame condition" if there are positive real numbers "A" and "B" such that <math> 0 and for each formula_8 in "V",
A set of vectors that satisfies the frame condition is a "frame" for the vector space.
The numbers "A" and "B" are called the lower and upper "frame bounds", respectively. The frame bounds are not unique because numbers less than "A" and greater than "B" are also valid frame bounds. The "optimal lower bound" is the supremum of all lower bounds and the "optimal upper bound" is the infimum of all upper bounds.
A frame is called "overcomplete" (or "redundant") if it is not a basis for the vector space.
Analysis operator.
The operator mapping formula_2 to a sequence of coefficients formula_4 is called the "analysis operator" of the frame. It is defined by:
By using this definition we may rewrite the frame condition as
where the left and right norms denote the norm in formula_7 and the middle norm is the formula_36 norm.
Synthesis operator.
The adjoint operator formula_37 of the analysis operator is called the "synthesis operator" of the frame. 
Motivation for the lower frame bound.
We want that any vector formula_39 can be reconstructed from the coefficients formula_40. This is satisfied if there exists a constant formula_41 such that for all formula_42 we have:
By setting formula_44 and applying the linearity of the analysis operator we get that this condition is equivalent to:
for all formula_39 which is exactly the lower frame bound condition.
History.
Because of the various mathematical components surrounding frames, frame theory has roots in harmonic and functional analysis, operator theory, linear algebra, and matrix theory.
The Fourier transform has been used for over a century as a way of decomposing and expanding signals. However, the Fourier transform masks key information regarding the moment of emission and the duration of a signal. In 1946, Dennis Gabor was able to solve this using a technique that simultaneously reduced noise, provided resiliency, and created quantization while encapsulating important signal characteristics. This discovery marked the first concerted effort towards frame theory.
The frame condition was first described by Richard Duffin and Albert Charles Schaeffer in a 1952 article on nonharmonic Fourier series as a way of computing the coefficients in a linear combination of the vectors of a linearly dependent spanning set (in their terminology, a "Hilbert space frame"). In the 1980s, Stéphane Mallat, Ingrid Daubechies, and Yves Meyer used frames to analyze wavelets. Today frames are associated with wavelets, signal and image processing, and data compression.
Relation to bases.
A frame satisfies a generalization of Parseval's identity, namely the frame condition, while still maintaining norm equivalence between a signal and its sequence of coefficients.
If the set formula_1 is a frame of "V", it spans "V". Otherwise there would exist at least one non-zero formula_2 which would be orthogonal to all formula_49. If we insert formula_8 into the frame condition, we obtain
therefore formula_52, which is a violation of the initial assumptions on the lower frame bound.
If a set of vectors spans "V", this is not a sufficient condition for calling the set a frame. As an example, consider formula_53 with the dot product, and the infinite set formula_1 given by
This set spans "V" but since formula_56, we cannot choose a finite upper frame bound "B". Consequently, the set formula_1 is not a frame.
Applications.
In signal processing, each vector is interpreted as a signal. In this interpretation, a vector expressed as a linear combination of the frame vectors is a redundant signal. Using a frame, it is possible to create a simpler, more sparse representation of a signal as compared with a family of elementary signals (that is, representing a signal strictly with a set of linearly independent vectors may not always be the most compact form). Frames, therefore, provide "robustness". Because they provide a way of producing the same vector within a space, signals can be encoded in various ways. This facilitates fault tolerance and resilience to a loss of signal. Finally, redundancy can be used to mitigate noise, which is relevant to the restoration, enhancement, and reconstruction of signals.
In signal processing, it is common to assume the vector space is a Hilbert space.
Special cases.
Tight frames.
A frame is a "tight frame" if "A" = "B"; in other words, the frame satisfies a generalized version of Parseval's identity. For example, the union of "k" disjoint orthonormal bases of a vector space is a tight frame with "A" = "B" = "k". A tight frame is a "Parseval frame" (sometimes called a "normalized frame") if "A" = "B" = 1. Each orthonormal basis is a Parseval frame, but the converse is not always true.
A frame formula_27 for formula_7 is tight with frame bound "A" if and only if
for all formula_61.
Equal norm frame.
A frame is an "equal norm frame" (sometimes called a "uniform frame" or a "normalized frame") if there is a constant "c" such that formula_62 for each "i". An equal norm frame is a "unit norm frame" if "c" = 1. A Parseval (or tight) unit norm frame is an orthonormal basis; such a frame satisfies Parseval's identity.
Equiangular frames.
A frame is an "equiangular frame" if there is a constant "c" such that formula_63 for each distinct "i" and "j".
Exact frames.
A frame is an "exact frame" if no proper subset of the frame spans the inner product space. Each basis for an inner product space is an exact frame for the space (so a basis is a special case of a frame).
Generalizations.
A "Bessel Sequence" is a set of vectors that satisfies only the upper bound of the frame condition.
Continuous Frame.
Suppose "H" is a Hilbert space, X a locally compact space , and formula_64 is a locally finite "Borel measure" on X. Then a set of vectors in "H", formula_65 with a measure formula_64 is said to be a "Continuous Frame" if there exists constants, formula_67 for all formula_68.
Example.
Given a discrete set formula_69 and a measure formula_70 where formula_71 is the "Dirac measure" then the continuous frame property:
 formula_72
reduces to:
formula_73
and we see that Continuous Frames are indeed the natural generalization of the frames mentioned above.
Just like in the discrete case we can define the Analysis, Synthesis, and Frame operators when dealing with continuous frames.
Continuous Analysis Operator.
Given a continuous frame formula_65 the "Continuous Analysis Operator" is the operator mapping formula_65 to a sequence of coefficients formula_76.
It is defined as follows:
formula_77 by formula_78
Continuous Synthesis Operator.
The adjoint operator of the Continuous Analysis Operator is the "Continuous Synthesis Operator" which is the map:
formula_79 by formula_80
Continuous Frame Operator.
The Composition of the Continuous Analysis Operator and the Continuous Synthesis Operator is known as the "Continuous Frame Operator". For a continuous frame formula_65, the "Continuous Frame Operator" is defined as follows:
formula_82 by formula_83
Continuous Dual Frame.
Given a continuous frame formula_65, and another continuous frame formula_85, then formula_85 is said to be a "Continuous Dual Frame" of formula_87 if it satisfies the following condition for all formula_88:
formula_89
Dual frames.
The frame condition entails the existence of a set of "dual frame vectors" formula_90 with the property that
for any formula_2. This implies that a frame together with its dual frame has the same property as a basis and its dual basis in terms of reconstructing a vector from scalar products.
In order to construct a dual frame, we first need the linear mapping formula_93, called the frame operator, defined as
From this definition of formula_95 and linearity in the first argument of the inner product,
which, when substituted in the frame condition inequality, yields
for each formula_2.
The frame operator formula_95 is self-adjoint, positive definite, and has positive upper and lower bounds. The inverse formula_100 of formula_95 exists and it, too, is self-adjoint, positive definite, and has positive upper and lower bounds.
The dual frame is defined by mapping each element of the frame with formula_100:
To see that this makes sense, let formula_8 be an element of formula_7 and let
Thus
which proves that
Alternatively, we can let
By inserting the above definition of formula_110 and applying the properties of formula_95 and its inverse,
which shows that
The numbers formula_114 are called "frame coefficients". This derivation of a dual frame is a summary of Section 3 in the article by Duffin and Schaeffer. They use the term "conjugate frame" for what here is called a dual frame.
The dual frame formula_115 is called the "canonical dual" of formula_3 because it acts similarly as a dual basis to a basis.
When the frame formula_3 is overcomplete, a vector formula_8 can be written as a linear combination of formula_3 in more than one way. That is, there are different choices of coefficients formula_120 such that formula_121. This allows us some freedom for the choice of coefficients formula_120 other than formula_114. It is necessary that the frame formula_3 is overcomplete for other such coefficients formula_120 to exist. If so, then there exist frames formula_126 for which 
for all formula_2. We call formula_129 a dual frame of formula_3.
Canonical duality is a reciprocity relation, i.e. if the frame formula_90 is the canonical dual frame of formula_6, then formula_6 is the canonical dual frame of formula_90.