Frame (linear algebra)

Short description: Similar to the basis of a vector space, but not necessarily linearly independent

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 [math]\displaystyle{ \{\mathbf{e}_k\} }[/math] in the vector space V and we want to express an arbitrary element [math]\displaystyle{ \mathbf{v} \in V }[/math] as a linear combination of the vectors [math]\displaystyle{ \{\mathbf{e}_{k}\} }[/math], that is, we want to find coefficients [math]\displaystyle{ c_k }[/math] such that

[math]\displaystyle{ \mathbf{v} = \sum_k c_k \mathbf{e}_k }[/math]

If the set [math]\displaystyle{ \{ \mathbf{e}_{k} \} }[/math] does not span [math]\displaystyle{ V }[/math], then such coefficients do not exist for every such [math]\displaystyle{ \mathbf{v} }[/math]. If [math]\displaystyle{ \{ \mathbf{e}_{k} \} }[/math] spans [math]\displaystyle{ V }[/math] and also is linearly independent, this set forms a basis of [math]\displaystyle{ V }[/math], and the coefficients [math]\displaystyle{ c_{k} }[/math] are uniquely determined by [math]\displaystyle{ \mathbf{v} }[/math]. If, however, [math]\displaystyle{ \{\mathbf{e}_{k}\} }[/math] spans [math]\displaystyle{ V }[/math] but is not linearly independent, the question of how to determine the coefficients becomes less apparent, in particular if [math]\displaystyle{ V }[/math] is of infinite dimension.

Given that [math]\displaystyle{ \{\mathbf{e}_k\} }[/math] spans [math]\displaystyle{ V }[/math] 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:

1. Removing arbitrary vectors from the set may cause it to be unable to span [math]\displaystyle{ V }[/math] before it becomes linearly independent.
2. Even if it is possible to devise a specific way to remove vectors from the set until it becomes a basis, this approach may become unfeasible in practice if the set is large or infinite.
3. In some applications, it may be an advantage to use more vectors than necessary to represent [math]\displaystyle{ \mathbf{v} }[/math]. This means that we want to find the coefficients [math]\displaystyle{ c_k }[/math] without removing elements in [math]\displaystyle{ \{\mathbf{e}_k\} }[/math]. The coefficients [math]\displaystyle{ c_k }[/math] will no longer be uniquely determined by [math]\displaystyle{ \mathbf{v} }[/math]. Therefore, the vector [math]\displaystyle{ \mathbf{v} }[/math] can be represented as a linear combination of [math]\displaystyle{ \{\mathbf{e}_{k}\} }[/math] in more than one way.

Formal definition

Let V be an inner product space and [math]\displaystyle{ \{\mathbf{e}_k\}_{k \in \mathbb{N}} }[/math] be a set of vectors in [math]\displaystyle{ V }[/math]. These vectors satisfy the frame condition if there are positive real numbers A and B such that [math]\displaystyle{ 0\lt A \le B \lt \infty }[/math] and for each [math]\displaystyle{ \mathbf{v} }[/math] in V,

[math]\displaystyle{ A \left\| \mathbf{v} \right\| ^2 \leq \sum_{k \in \mathbb{N}} \left| \langle \mathbf{v}, \mathbf{e}_k \rangle \right| ^2 \leq B \left\| \mathbf{v} \right\| ^2 . }[/math]

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 [math]\displaystyle{ \mathbf{v} \in V }[/math] to a sequence of coefficients [math]\displaystyle{ c_k }[/math] is called the analysis operator of the frame. It is defined by:

[math]\displaystyle{ \mathbf{T}: V \to \ell^2, \quad \mathbf{v} \mapsto \{c_k\}_{k \in \mathbb{N}}, \quad c_k = \langle \mathbf{v},\mathbf{e_k}\rangle }[/math]

By using this definition we may rewrite the frame condition as

[math]\displaystyle{ A \left\| \mathbf{v} \right\| ^2 \leq \left\| \mathbf{T} \mathbf{v} \right\| ^2 \leq B \left\| \mathbf{v} \right\| ^2 }[/math]

where the left and right norms denote the norm in [math]\displaystyle{ V }[/math] and the middle norm is the [math]\displaystyle{ \ell ^2 }[/math] norm.

Synthesis operator

The adjoint operator [math]\displaystyle{ \mathbf{T}^* }[/math] of the analysis operator is called the synthesis operator of the frame.

[math]\displaystyle{ \mathbf{T}^*: \ell^2 \to V, \quad \{c_k\}_{k \in \mathbb{N}} \mapsto \mathbf{v}, \quad \mathbf{v} = \sum_k c_k\mathbf{e}_k }[/math]

Motivation for the lower frame bound

We want that any vector [math]\displaystyle{ v \in V }[/math] can be reconstructed from the coefficients [math]\displaystyle{ \{ \langle v,\mathbf{e}_k\rangle \}_{k \in \mathbb{N}} }[/math]. This is satisfied if there exists a constant [math]\displaystyle{ A \gt 0 }[/math] such that for all [math]\displaystyle{ x,y \in V }[/math] we have:

[math]\displaystyle{ A \| x-y \|^2 \le \| Tx-Ty \|^2 }[/math]

By setting [math]\displaystyle{ v=x-y }[/math] and applying the linearity of the analysis operator we get that this condition is equivalent to:

[math]\displaystyle{ A \| v \|^2 \le \| Tv \|^2 }[/math]

for all [math]\displaystyle{ v \in V }[/math] 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 [math]\displaystyle{ \{\mathbf{e}_k\} }[/math] is a frame of V, it spans V. Otherwise there would exist at least one non-zero [math]\displaystyle{ \mathbf{v} \in V }[/math] which would be orthogonal to all [math]\displaystyle{ \mathbf{e}_k }[/math]. If we insert [math]\displaystyle{ \mathbf{v} }[/math] into the frame condition, we obtain

[math]\displaystyle{ A \left\| \mathbf{v} \right\| ^2 \leq 0 \leq B \left\| \mathbf{v} \right\| ^{2} ; }[/math]

therefore [math]\displaystyle{ v = 0 }[/math], contradicting our assumption, or [math]\displaystyle{ A \leq 0 }[/math], 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 [math]\displaystyle{ V = \mathbb{R}^2 }[/math] with the dot product, and the infinite set [math]\displaystyle{ \{\mathbf{e}_k\} }[/math] given by

[math]\displaystyle{ \left\{ (1,0) , \, (0,1), \, \left(0,\tfrac{1}{\sqrt{2}}\right) , \, \left(0,\tfrac{1}{\sqrt{3}}\right), \dotsc \right\}. }[/math]

This set spans V but since [math]\displaystyle{ \sum_k \left| \langle \mathbf{e}_k , (0,1)\rangle \right| ^2 = 0 + 1 + \tfrac{1}{2} + \tfrac{1}{3} +\dotsb = \infty }[/math], we cannot choose a finite upper frame bound B. Consequently, the set [math]\displaystyle{ \{\mathbf{e}_k\} }[/math] 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 [math]\displaystyle{ \{\mathbf{e}_k\}_{k \in \mathbb{N}} }[/math] for [math]\displaystyle{ V }[/math] is tight with frame bound A if and only if

[math]\displaystyle{ v = \frac{1}{A} \sum_k \langle \mathbf{v},\mathbf{e}_k\rangle \mathbf{e}_k }[/math]

for all [math]\displaystyle{ v \in V }[/math].

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 [math]\displaystyle{ \|e_i\| = c }[/math] 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 [math]\displaystyle{ | \langle e_i, e_j \rangle | = c }[/math] 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 [math]\displaystyle{ \mu }[/math] is a locally finite Borel measure on X. Then a set of vectors in H, [math]\displaystyle{ \{f_x\}_{x\in X} }[/math] with a measure [math]\displaystyle{ \mu }[/math] is said to be a Continuous Frame if there exists constants, [math]\displaystyle{ 0\lt A\leq B }[/math] such that [math]\displaystyle{ A||f||^2\leq \int_{X}|\langle f,f_x\rangle|^2d\mu(x)\leq B||f||^2 }[/math] for all [math]\displaystyle{ f\in H }[/math].

Example

Given a discrete set [math]\displaystyle{ \Lambda\subset X }[/math] and a measure [math]\displaystyle{ \mu= \delta_\Lambda }[/math] where [math]\displaystyle{ \delta_\Lambda }[/math] is the Dirac measure then the continuous frame property

[math]\displaystyle{ A||f||^2\leq \int_{X}|\langle f,f_x\rangle|^2d\mu(x)\leq B||f||^2 }[/math]

reduces to

[math]\displaystyle{ A||f||^2\leq \sum_{\lambda\in \Lambda}|\langle f,f_{\lambda}\rangle|^2\leq B||f||^2 }[/math].

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 [math]\displaystyle{ \{f_x\}_{x\in X} }[/math] the continuous analysis operator is the operator mapping [math]\displaystyle{ \{f_x\}_{x\in X} }[/math] to a sequence of coefficients [math]\displaystyle{ \langle f,f_x\rangle _{x\in X} }[/math].

It is defined as follows:

[math]\displaystyle{ T:H \mapsto L^2(X,\mu) }[/math] by [math]\displaystyle{ f \to \langle f,f_x\rangle _{x\in X} }[/math].

Continuous synthesis operator

The adjoint operator of the continuous analysis operator is the continuous synthesis operator, which is the map

[math]\displaystyle{ T^*:L^2(X,\mu) \mapsto H }[/math] by [math]\displaystyle{ a_x \to\int_X a_x f_x d\mu(x) }[/math].

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 [math]\displaystyle{ \{f_x\}_{x\in X} }[/math], it is defined as follows:

[math]\displaystyle{ S:H\mapsto H }[/math] by [math]\displaystyle{ Sf:=\int_X \langle f,f_x\rangle f_x d\mu(x) }[/math].

Continuous dual frame

Given a continuous frame [math]\displaystyle{ \{f_x\}_{x\in X} }[/math], and another continuous frame [math]\displaystyle{ \{g_x\}_{x\in X} }[/math], then [math]\displaystyle{ \{g_x\}_{x\in X} }[/math] is said to be a continuous dual frame of [math]\displaystyle{ \{f_x\} }[/math] if it satisfies the following condition for all [math]\displaystyle{ f, h\in H }[/math]:

[math]\displaystyle{ \langle f, h\rangle =\int_X\langle f,f_x\rangle \langle g_x, h\rangle d\mu(x) }[/math].

Dual frames

The frame condition entails the existence of a set of dual frame vectors [math]\displaystyle{ \{ \mathbf{\tilde{e}}_{k} \} }[/math] with the property that

[math]\displaystyle{ \mathbf{v} = \sum_k \langle \mathbf{v} , \mathbf{\tilde{e}}_k \rangle \mathbf{e}_k = \sum_k \langle \mathbf{v} , \mathbf{e}_k \rangle \mathbf{\tilde{e}}_k }[/math]

for any [math]\displaystyle{ \mathbf{v} \in V. }[/math] 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 [math]\displaystyle{ \mathbf{S} : V \rightarrow V, }[/math] called the frame operator, defined as

[math]\displaystyle{ \mathbf{S} \mathbf{v} = \sum_{k} \langle \mathbf{v} , \mathbf{e}_{k} \rangle \mathbf{e}_{k} = \mathbf{T}^*\mathbf{T}\mathbf{v}. }[/math]

From this definition of [math]\displaystyle{ \mathbf{S} }[/math] and linearity in the first argument of the inner product,

[math]\displaystyle{ \langle \mathbf{S} \mathbf{v} , \mathbf{v} \rangle = \sum_k \left| \langle \mathbf{v} , \mathbf{e}_k \rangle \right| ^2 , }[/math]

which, when substituted in the frame condition inequality, yields

[math]\displaystyle{ A \left\| \mathbf{v} \right\| ^2 \leq \langle \mathbf{S} \mathbf{v} , \mathbf{v} \rangle \leq B \left\| \mathbf{v} \right\| ^2 , }[/math]

for each [math]\displaystyle{ \mathbf{v} \in V. }[/math]

The frame operator [math]\displaystyle{ \mathbf{S} }[/math] is self-adjoint, positive definite, and has positive upper and lower bounds. The inverse [math]\displaystyle{ \mathbf{S}^{-1} }[/math] of [math]\displaystyle{ \mathbf{S} }[/math] 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 [math]\displaystyle{ \mathbf{S}^{-1} }[/math]:

[math]\displaystyle{ \tilde{\mathbf{e}}_{k} = \mathbf{S}^{-1} \mathbf{e}_{k} }[/math]

To see that this makes sense, let [math]\displaystyle{ \mathbf{v} }[/math] be an element of [math]\displaystyle{ V }[/math] and let

[math]\displaystyle{ \mathbf{u} = \sum_{k} \langle \mathbf{v} , \mathbf{e}_{k} \rangle \tilde{\mathbf{e}}_{k}. }[/math]

Thus

[math]\displaystyle{ \mathbf{u} = \sum_{k} \langle \mathbf{v} , \mathbf{e}_{k} \rangle ( \mathbf{S}^{-1} \mathbf{e}_{k} ) = \mathbf{S}^{-1} \left ( \sum_{k} \langle \mathbf{v} , \mathbf{e}_{k} \rangle \mathbf{e}_{k} \right ) = \mathbf{S}^{-1} \mathbf{S} \mathbf{v} = \mathbf{v}, }[/math]

which proves that

[math]\displaystyle{ \mathbf{v} = \sum_{k} \langle \mathbf{v} , \mathbf{e}_{k} \rangle \tilde{\mathbf{e}}_{k}. }[/math]

Alternatively, we can let

[math]\displaystyle{ \mathbf{u} = \sum_{k} \langle \mathbf{v} , \tilde{\mathbf{e}}_{k} \rangle \mathbf{e}_{k}. }[/math]

By inserting the above definition of [math]\displaystyle{ \tilde{\mathbf{e}}_{k} }[/math] and applying the properties of [math]\displaystyle{ \mathbf{S} }[/math] and its inverse,

[math]\displaystyle{ \mathbf{u} = \sum_{k} \langle \mathbf{v} , \mathbf{S}^{-1} \mathbf{e}_{k} \rangle \mathbf{e}_{k} = \sum_{k} \langle \mathbf{S}^{-1} \mathbf{v} , \mathbf{e}_{k} \rangle \mathbf{e}_{k} = \mathbf{S} (\mathbf{S}^{-1} \mathbf{v}) = \mathbf{v} }[/math]

which shows that

[math]\displaystyle{ \mathbf{v} = \sum_{k} \langle \mathbf{v} , \tilde{\mathbf{e}}_{k} \rangle \mathbf{e}_{k}. }[/math]

The numbers [math]\displaystyle{ \langle \mathbf{v} , \tilde{\mathbf{e}}_{k} \rangle }[/math] 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 [math]\displaystyle{ \{\tilde{\mathbf{e}}_{k}\} }[/math] is called the canonical dual of [math]\displaystyle{ \{\mathbf{e}_{k}\} }[/math] because it acts similarly as a dual basis to a basis.

When the frame [math]\displaystyle{ \{\mathbf{e}_{k}\} }[/math] is overcomplete, a vector [math]\displaystyle{ \mathbf{v} }[/math] can be written as a linear combination of [math]\displaystyle{ \{\mathbf{e}_{k}\} }[/math] in more than one way. That is, there are different choices of coefficients [math]\displaystyle{ \{c_{k}\} }[/math] such that [math]\displaystyle{ \mathbf{v} = \sum_{k} c_{k} \mathbf{e}_{k}. }[/math] This allows us some freedom for the choice of coefficients [math]\displaystyle{ \{c_{k}\} }[/math] other than [math]\displaystyle{ \langle \mathbf{v} , \tilde{\mathbf{e}}_{k} \rangle. }[/math] It is necessary that the frame [math]\displaystyle{ \{\mathbf{e}_{k}\} }[/math] is overcomplete for other such coefficients [math]\displaystyle{ \{c_{k}\} }[/math] to exist. If so, then there exist frames [math]\displaystyle{ \{\mathbf{g}_{k}\} \neq \{\tilde{\mathbf{e}}_{k}\} }[/math] for which

[math]\displaystyle{ \mathbf{v} = \sum_{k} \langle \mathbf{v} , \mathbf{g}_{k} \rangle \mathbf{e}_{k} }[/math]

for all [math]\displaystyle{ \mathbf{v} \in V. }[/math] We call [math]\displaystyle{ \{\mathbf{g}_{k}\} }[/math] a dual frame of [math]\displaystyle{ \{\mathbf{e}_{k}\}. }[/math]

Canonical duality is a reciprocity relation, i.e. if the frame [math]\displaystyle{ \{ \mathbf{\tilde{e}}_{k} \} }[/math] is the canonical dual frame of [math]\displaystyle{ \{ \mathbf{e}_{k} \}, }[/math] then [math]\displaystyle{ \{ \mathbf{e}_{k} \} }[/math] is the canonical dual frame of [math]\displaystyle{ \{ \mathbf{\tilde{e}}_{k} \}. }[/math]

See also

• k-frame
• Biorthogonal wavelet
• Orthogonal wavelet
• Restricted isometry property
• Schauder basis
• Harmonic analysis
• Fourier analysis
• Functional analysis

References

• Casazza, Peter; Kutyniok, Gitta; Philipp, Friedrich (2013). "Introduction to Finite Frame Theory". Finite Frames: Theory and Applications. Berlin: Birkhäuser. pp. 1–53. ISBN 978-0-8176-8372-6. 
• Christensen, Ole (2003). An Introduction to Frames and Riesz Bases. Applied and Numerical Harmonic Analysis. Birkhäuser. doi:10.1007/978-0-8176-8224-8. ISBN 978-1-4612-6500-9. 
• Duffin, Richard James; Schaeffer, Albert Charles (1952). "A class of nonharmonic Fourier series". Transactions of the American Mathematical Society 72 (2): 341–366. doi:10.2307/1990760. 
• Kovačević, Jelena; Chebira, Amina (2008). "An Introduction to Frames". Foundations and Trends in Signal Processing 2 (1): 1–94. doi:10.1561/2000000006. http://infoscience.epfl.ch/record/133268/files/08_KovacevicC_F%26T.pdf. 
• Kovacevic, Jelena; Dragotti, Pier Luigi; Goyal, Vivek (2002). "Filter Bank Frame Expansions with Erasures". IEEE Transactions on Information Theory 48 (6): 1439–1450. doi:10.1109/TIT.2002.1003832. http://citeseer.ist.psu.edu/cache/papers/cs/28168/http:zSzzSzlcavwww.epfl.chzSz~dragottizSzpublicationszSzIT_june02.pdf/kovacevic02filter.pdf. 
• Mallat, Stéphane (2009). A Wavelet Tour of Signal Processing: The Sparse Way (3rd ed.). Academic Press. ISBN 978-0-12-374370-1. http://links.uwaterloo.ca/amath391w13docs/Mallat3.pdf. Retrieved 2020-08-01.