Frame (linear algebra)

(Redirected from Frame (signal processing))

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.[1] 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.[2]

History

edit

Because of the various mathematical components surrounding frames, frame theory has roots in harmonic and functional analysis, operator theory, linear algebra, and matrix theory.[3]

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.[1] 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").[4] 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.

Definition and motivation

edit

Motivating example: computing a basis from a linearly dependent set

edit

Suppose we have a vector space   over a field   and we want to express an arbitrary element   as a linear combination of the vectors  , that is, finding coefficients   such that

 

If the set   does not span  , then such coefficients do not exist for every such  . If   spans   and also is linearly independent, this set forms a basis of  , and the coefficients   are uniquely determined by  . If, however,   spans   but is not linearly independent, the question of how to determine the coefficients becomes less apparent, in particular if   is of infinite dimension.

Given that   spans   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   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  . This means that we want to find the coefficients   without removing elements in  . The coefficients   will no longer be uniquely determined by  . Therefore, the vector   can be represented as a linear combination of   in more than one way.

Definition

edit

Let   be an inner product space and   be a set of vectors in  . The set   is a frame of   if it satisfies the so called frame condition. That is, if there exist two constants   such that[5]

 

A frame is called overcomplete (or redundant) if it is not a Riesz basis for the vector space. The redundancy of the frame is measured by the lower and upper frame bounds (or redundancy factors)   and  , respectively.[6] That is, a frame of   normalized vectors   in an  -dimensional space   has frame bounds which satisfiy

 

If the frame is a Riesz basis and is therefore linearly independent, then  .

The frame bounds are not unique because numbers less than   and greater than   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.

Analysis operator

edit

If the frame condition is satisfied, then the linear operator defined as[7]

 

mapping   to the sequence of frame coefficients  , is called the analysis operator. Using this definition, the frame condition can be rewritten as

 

Synthesis operator

edit

The adjoint of the analysis operator is called the synthesis operator of the frame and defined as[8]

 

Frame operator

edit

The composition of the analysis operator and the synthesis operator leads to the frame operator defined as

 

From this definition and linearity in the first argument of the inner product, the frame condition now yields

 

If the analysis operator exists, then so does the frame operator   as well as the inverse  . Both   and   are positive definite, bounded self-adjoint operators, resulting in   and   being the infimum and supremum values of the spectrum of  .[9] In finite dimensions, the frame operator is automatically trace-class, with   and   corresponding to the smallest and largest eigenvalues of   or, equivalently, the smallest and largest singular values of  .[10]

Relation to bases

edit

The frame condition is a generalization of Parseval's identity that maintains norm equivalence between a signal in   and its sequence of coefficients in  .

If the set   is a frame of  , it spans  . Otherwise there would exist at least one non-zero   which would be orthogonal to all   such that

 

either violating the frame condition or the assumption that  .

However, a spanning set of   is not necessarily a frame. For example, consider   with the dot product, and the infinite set   given by

 

This set spans   but since

 

we cannot choose a finite upper frame bound B. Consequently, the set   is not a frame.

Dual frames

edit

Let   be a frame; satisfying the frame condition. Then the dual operator is defined as

 

with

 

called the dual frame (or conjugate frame). It is the canonical dual of   (similar to a dual basis of a basis), with the property that[11]

 

and subsequent frame condition

 

Canonical duality is a reciprocity relation, i.e. if the frame   is the canonical dual of   then the frame   is the canonical dual of   To see that this makes sense, let   be an element of   and let

 

Thus

 

proving that

 

Alternatively, let

 

Applying the properties of   and its inverse then shows that

 

and therefore

 

An overcomplete frame   allows us some freedom for the choice of coefficients   such that  . That is, there exist dual frames   of   for which

 

Dual frame synthesis and analysis

edit

Suppose   is a subspace of a Hilbert space   and let   and   be a frame and dual frame of  , respectively. If   does not depend on  , the dual frame is computed as

 

where   denotes the restriction of   to   such that   is invertible on  . The best linear approximation of   in   is then given by the orthogonal projection of   onto  , defined as

 

The dual frame synthesis operator is defined as

 

and the orthogonal projection is computed from the frame coefficients  . In dual analysis, the orthogonal projection is computed from   as

 

with dual frame analysis operator  .[12]

Applications and examples

edit

In signal processing, it is common to represent signals as vectors in a Hilbert space. In this interpretation, a vector expressed as a linear combination of the frame vectors is a redundant signal. Representing a signal strictly with a set of linearly independent vectors may not always be the most compact form.[13] Using a frame, it is possible to create a simpler, more sparse representation of a signal as compared with a family of elementary signals. 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.

Non-harmonic Fourier series

edit

From Harmonic analysis it is known that the complex trigonometric system   form an orthonormal basis for  . As such,   is a (tight) frame for   with bounds  .[14]

The system remains stable under "sufficiently small" perturbations   and the frame   will form a Riesz basis for  . Accordingly, every function   in   will have a unique non-harmonic Fourier series representation

 

with   and   is called the Fourier frame (or frame of exponentials). What constitutes "sufficiently small" is described by the following theorem, named after Mikhail Kadets.[15]

Kadec's 14-theorem — Let   be a sequence of real numbers such that

 

then   satisfies the Paley-Wiener criterion and thus forms a Riesz basis for  .

The theorem can be easily extended to frames, replacing the integers by another sequence of real numbers   such that[16][17]

 

then   is a frame for   with bounds

 

Frame projector

edit

Redundancy of a frame is useful in mitigating added noise from the frame coefficients. Let   denote a vector computed with noisy frame coefficients. The noise is then mitigated by projecting   onto the image of  .

Theorem — Let   be a frame of a Hilbert space of subspace thereof. The orthogonal projection   is

 

The coefficients   are frame coefficients   in   if and only if

 

The   sequence space and   (as  ) are reproducing kernel Hilbert spaces with a kernel given by the matrix  .[9] As such, the above equation is also referred to as the reproducing kernel equation and expresses the redundancy of frame coefficients.[18]

Special cases

edit

Tight frames

edit

A frame is a tight frame if  . A tight frame   with frame bound   has the property that

 

For example, the union of   disjoint orthonormal bases of a vector space is an overcomplete tight frame with  . A tight frame is a Parseval frame if  .[19] Each orthonormal basis is a (complete) Parseval frame, but the converse is not necessarily true.[20]

Equal norm frame

edit

A frame is an equal norm frame if there is a constant   such that   for each  . An equal norm frame is a normalized frame (sometimes called a unit-norm frame) if  .[21] A unit-norm Parseval frame is an orthonormal basis; such a frame satisfies Parseval's identity.

Equiangular frames

edit

A frame is an equiangular frame if there is a constant   such that   for all  . In particular, every orthonormal basis is equiangular.[22]

Exact frames

edit

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

edit

Semi-frame

edit

Sometimes it may not be possible to satisfy both frame bounds simultaneously. An upper (respectively lower) semi-frame is a set that only satisfies the upper (respectively lower) frame inequality.[9] The Bessel Sequence is an example of a set of vectors that satisfies only the upper frame inequality.

For any vector   to be reconstructed from the coefficients   it suffices if there exists a constant   such that

 

By setting   and applying the linearity of the analysis operator, this condition is equivalent to:

 

which is exactly the lower frame bound condition.

Fusion frame

edit

A fusion frame is best understood as an extension of the dual frame synthesis and analysis operators where, instead of a single subspace  , a set of closed subspaces   with positive scalar weights   is considered. A fusion frame is a family   that satisfies the frame condition

 

where   denotes the orthogonal projection onto the subspace  .[23]

Continuous frame

edit

Suppose   is a Hilbert space,   a locally compact space, and   is a locally finite Borel measure on  . Then a set of vectors in  ,   with a measure   is said to be a continuous frame if there exists constants,   such that

 

To see that continuous frames are indeed the natural generalization of the frames mentioned above, consider a discrete set   and a measure   where   is the Dirac measure. Then the continuous frame condition reduces to

 

Just like in the discrete case we can define the analysis, synthesis, and frame operators when dealing with continuous frames.

Continuous analysis operator

edit

Given a continuous frame   the continuous analysis operator is the operator mapping   to a function on   defined as follows:

  by  .

Continuous synthesis operator

edit

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

  by  .

Continuous frame operator

edit

The composition of the continuous analysis operator and the continuous synthesis operator is known as the continuous frame operator. For a continuous frame  , it is defined as follows:

  by  

In this case, the continuous frame projector   is the orthogonal projection defined by

 

The projector   is an integral operator with reproducting kernel  , thus   is a reproducing kernel Hilbert space.[9]

Continuous dual frame

edit

Given a continuous frame  , and another continuous frame  , then   is said to be a continuous dual frame of   if it satisfies the following condition for all  :

 

Framed positive operator-valued measure

edit

Just as a frame is a natural generalization of a basis to sets that may be linear dependent, a positive operator-valued measure (POVM) is a natural generalization of a projection-valued measure (PVM) in that elements of a POVM are not necessarily orthogonal projections.

Suppose   is a measurable space with   a Borel σ-algebra on   and let   be a POVM from   to the space of positive operators on   with the additional property that

 

where   is the identity operator. Then   is called a framed POVM.[23]

In case of the fusion frame condition, this allows for the substitution

 

For the continuous frame operator, the framed POVM would be[24]

 

See also

edit

Notes

edit

References

edit
  • Antoine, J.-P.; Balazs, P. (2012). "Frames, Semi-Frames, and Hilbert Scales". Numerical Functional Analysis and Optimization. 33 (7–9): 736–769. arXiv:1203.0506. doi:10.1080/01630563.2012.682128. ISSN 0163-0563.
  • 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 (2016). "An Introduction to Frames and Riesz Bases". Applied and Numerical Harmonic Analysis. Cham: Springer International Publishing. doi:10.1007/978-3-319-25613-9. ISBN 978-3-319-25611-5. ISSN 2296-5009.
  • 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. JSTOR 1990760. MR 0047179.
  • Kovačević, Jelena; Chebira, Amina (2008). "An Introduction to Frames" (PDF). Foundations and Trends in Signal Processing. 2 (1): 1–94. doi:10.1561/2000000006.
  • Kovacevic, Jelena; Dragotti, Pier Luigi; Goyal, Vivek (2002). "Filter Bank Frame Expansions with Erasures" (PDF). IEEE Transactions on Information Theory. 48 (6): 1439–1450. CiteSeerX 10.1.1.661.2699. doi:10.1109/TIT.2002.1003832.
  • Mallat, Stéphane (2009). A wavelet tour of signal processing: the sparse way. Amsterdam Boston: Elsevier/Academic Press. ISBN 978-0-12-374370-1.
  • Moran, Bill; Howard, Stephen; Cochran, Doug (2013). "Positive-Operator-Valued Measures: A General Setting for Frames". Excursions in Harmonic Analysis, Volume 2. Boston: Birkhäuser Boston. doi:10.1007/978-0-8176-8379-5_4. ISBN 978-0-8176-8378-8.
  • Robinson, Benjamin; Moran, Bill; Cochran, Doug (2021). "Positive operator-valued measures and densely defined operator-valued frames". Rocky Mountain Journal of Mathematics. 51 (1). arXiv:2004.11729. doi:10.1216/rmj.2021.51.265. ISSN 0035-7596.
  • Young, Robert M. (2001). An Introduction to Non-Harmonic Fourier Series, Revised Edition, 93. Academic Press. ISBN 978-0-12-772955-8.