en>Ag2gaeh: /* Miquelian Minkowski planes */ hint on the non existence of "ovoidal Minkowski planes" added

2013-07-30T16:08:12Z

Miquelian Minkowski planes: hint on the non existence of "ovoidal Minkowski planes" added

New page

{{about|a generalization of bases to linearly dependent sets of vectors|a linearly independent set of vectors|k-frame}}

In [[linear algebra]], a '''frame of a vector space''' ''V'' with an [[inner product]] can be seen as a generalization of the idea of a [[Basis (linear algebra)|basis]] to sets which may be [[linearly dependent]]. Frames were introduced by Duffin and Schaeffer in their study on [[nonharmonic Fourier series]]. They remained obscure until [[Stéphane Mallat|Mallat]], [[Ingrid Daubechies|Daubechies]], and others used them to analyze [[wavelets]] in the 1980s. Some practical uses of frames today include robust [[Error detection and correction|coding]] and design and analysis of [[filter bank]]s.

The key issue related to the construction of a frame appears when we have a sequence of vectors <math>\{\mathbf{e}_{k}\}</math>, with each <math>\mathbf{e}_{k} \in V</math> and we want to express an arbitrary element <math>\mathbf{v} \in V</math> as a linear combination of the vectors <math>\{\mathbf{e}_{k}\}</math>:

:<math> \mathbf{v} = \sum_{k} c_{k} \mathbf{e}_{k} </math>

and want to determine the coefficients <math>c_{k}</math>. If the set <math>\{ \mathbf{e}_{k} \}</math> does not span <math>V</math>, then these coefficients cannot be determined for all such <math>\mathbf{v}</math>. If <math>\{ \mathbf{e}_{k} \}</math> spans <math>V</math> and also is [[linearly independent]], this set forms a [[Basis (linear algebra)|basis]] of <math>V</math>, and the coefficients <math>c_{k}</math> are uniquely determined by <math>\mathbf{v}</math>: they are the [[coordinate]]s of <math>\mathbf{v}</math> relative to this basis. If, however, <math>\{\mathbf{e}_{k}\}</math> spans <math>V</math> but is not linearly independent, the question of how to determine the coefficients becomes less apparent, in particular if <math>V</math> is of infinite dimension.

Given that <math>\{\mathbf{e}_{k}\}</math> spans <math>V</math> and is linearly dependent, it may appear obvious that we should remove vectors from the set until it becomes linearly independent and forms a basis. There are some problems with this strategy:

# By removing vectors randomly from the set, it may lose its possibility to span <math>V</math> before it becomes linearly independent.
# 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 infeasible in practice if the set is large or infinite.
# In some applications, it may be an advantage to use more vectors than necessary to represent <math>\mathbf{v}</math>. This means that we want to find the coefficients <math>c_{k}</math> without removing elements in <math>\{\mathbf{e}_{k}\}</math>.

In 1952, Duffin and Schaeffer gave a solution to this problem, by describing a condition on the set <math>\{ \mathbf{e}_{k} \}</math> that makes it possible to compute the coefficients <math>c_{k}</math> in a simple way. More precisely, a ''frame'' is a set <math>\{ \mathbf{e}_{k} \}</math> of elements of ''V'' which satisfy the so-called ''frame condition:''

:There exist two real numbers, ''A'' and ''B'' such that <math>0 < A \leq B < \infty</math> and
::<math>A \| \mathbf{v} \|^{2} \leq \sum_{k} |\langle \mathbf{v} \mid \mathbf{e}_{k} \rangle|^{2} \leq B \| \mathbf{v} \|^{2}
\text{ for all }\mathbf{v} \in V</math>.
: This means that the constants ''A'' and ''B'' can be chosen independently of '''v''': they only depend on the set <math>\{\mathbf{e}_{k}\}</math>.

The numbers ''A'' and ''B'' are called lower and upper ''frame bounds''.

It can be shown that the frame condition entails the existence of a set of ''dual frame vectors'' <math>\{ \mathbf{\tilde{e}}_{k} \}</math> with the property that

:<math>
\sum_{k} \langle \mathbf{v} \mid \mathbf{\tilde{e}}_{k} \rangle \mathbf{e}_{k} =
\sum_{k} \langle \mathbf{v} \mid \mathbf{e}_{k} \rangle \mathbf{\tilde{e}}_{k} = \mathbf{v}
</math>

for any <math>\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.

== Relation to bases ==
If the set <math>\{\mathbf{e}_{k}\}</math> is a frame of ''V'', it spans ''V''. Otherwise there would exist at least one non-zero <math>\mathbf{v} \in V</math> which would be orthogonal to all <math>\mathbf{e}_{k}</math>. If we insert <math>\mathbf{v}</math> into the frame condition, we obtain

:<math>
A \| \mathbf{v} \|^{2} \leq 0 \leq B \| \mathbf{v} \|^{2} ;
</math>

therefore <math>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> V = \mathbb{R}^{2}</math> and the infinite set <math>\{\mathbf{e}_{k}\}</math> given by

:<math>\left\{ (1,0) , \, (0,1), \, \left(0,\frac{1}{\sqrt{2}}\right) , \, \left(0,\frac{1}{\sqrt{3}}\right), \ldots \right\}.</math>

This set spans ''V'' but since <math>\sum_k \mid \langle \mathbf{e}_k|(0,1)\rangle|^2 = 0 + 1 + \frac{1}{2} + \frac{1}{3} +\cdots = \infty</math> we cannot choose <math>B < \infty</math>. Consequently, the set <math>\{\mathbf{e}_{k}\}</math> is not a frame.

== Types of frames ==
=== Tight frames ===

A frame is '''tight''' if the frame bounds <math>A</math> and <math>B</math> are equal. This means that the frame obeys a generalized [[Parseval's identity]]. For example, the union of <math>k</math> [[orthonormal basis| orthonormal bases]] of a vector space forms a tight frame with <math>A = B = k</math>. If <math>A = B = 1</math>, then a frame is either called '''normalized''' or '''Parseval'''. However, some of the literature refers to a frame for which <math>\forall k\ \|\mathbf{e}_k\| = c </math> where <math> c </math> is a constant independent of <math>k</math> (see '''uniform''' below) as a '''normalized''' frame.

=== Uniform frames ===

A frame is '''uniform''' if each element has the same norm: <math>\forall k\ \|\mathbf{e}_k\| = c </math> where <math> c </math> is a constant independent of <math>k</math>.
A uniform normalized tight frame with <math>c=1</math> is an [[orthonormal basis]].

== The dual frame ==

The frame condition is both sufficient and necessary for allowing the construction of a dual or conjugate frame, <math> \{ \tilde{\mathbf{e}}_{k} \}</math>, relative the original frame, <math> \{ \mathbf{e}_{k} \}</math>. The duality of this frame implies that

:<math>
\sum_{k} \langle \mathbf{v} \mid \mathbf{\tilde{e}}_{k} \rangle \mathbf{e}_{k} =
\sum_{k} \langle \mathbf{v} \mid \mathbf{e}_{k} \rangle \mathbf{\tilde{e}}_{k} = \mathbf{v}
</math>

is satisfied for all <math>\mathbf{v} \in V</math>. In order to construct the dual frame, we first need the linear mapping: <math>\mathbf{S} : V \rightarrow V</math> defined as

:<math>
\mathbf{S} \mathbf{v} = \sum_{k} \langle \mathbf{v} \mid \mathbf{e}_{k} \rangle \mathbf{e}_{k}
</math>

From this definition of <math>\mathbf{S}</math> and linearity in the first argument of the inner product, it now follows that

:<math>
\langle \mathbf{S} \mathbf{v} \mid \mathbf{v} \rangle =
\sum_{k} |\langle \mathbf{v} \mid \mathbf{e}_{k} \rangle|^{2}
</math>

which can be inserted into the frame condition to get

:<math>A \| \mathbf{v} \|^{2} \leq
\langle \mathbf{S} \mathbf{v} \mid \mathbf{v} \rangle \leq B \| \mathbf{v} \|^{2}
\text{ for all }\mathbf{v} \in V</math>

The properties of <math>\mathbf{S}</math> can be summarised as follows:

# <math>\mathbf{S}</math> is [[self-adjoint]], [[positive definite]], and has positive upper and lower bounds. This leads to
# the inverse <math>\mathbf{S}^{-1}</math> of <math>\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>\mathbf{S}^{-1}</math>:

:<math>
\tilde{\mathbf{e}}_{k} = \mathbf{S}^{-1} \mathbf{e}_{k}
</math>

To see that this makes sense, let <math>\mathbf{v} \in V</math> be arbitrary and set

:<math>
\mathbf{u} =
\sum_{k} \langle \mathbf{v} \mid \mathbf{e}_{k} \rangle \tilde{\mathbf{e}}_{k}
</math>

It is then the case that

:<math>
\mathbf{u} =
\sum_{k} \langle \mathbf{v} \mid \mathbf{e}_{k} \rangle ( \mathbf{S}^{-1} \mathbf{e}_{k} ) =
\mathbf{S}^{-1} \left ( \sum_{k} \langle \mathbf{v} \mid \mathbf{e}_{k} \rangle \mathbf{e}_{k} \right ) =
\mathbf{S}^{-1} \mathbf{S} \mathbf{v} = \mathbf{v}
</math>

which proves that

:<math>
\mathbf{v} = \sum_{k} \langle \mathbf{v} \mid \mathbf{e}_{k} \rangle \tilde{\mathbf{e}}_{k}
</math>

Alternatively, we can set

:<math>
\mathbf{u} = \sum_{k} \langle \mathbf{v} \mid \tilde{\mathbf{e}}_{k} \rangle \mathbf{e}_{k}
</math>

By inserting the above definition of <math>\tilde{\mathbf{e}}_{k}</math> and applying known properties of <math>\mathbf{S}</math> and its inverse, we get

:<math>
\mathbf{u} =
\sum_{k} \langle \mathbf{v} \mid \mathbf{S}^{-1} \mathbf{e}_{k} \rangle \mathbf{e}_{k} =
\sum_{k} \langle \mathbf{S}^{-1} \mathbf{v} \mid \mathbf{e}_{k} \rangle \mathbf{e}_{k} =
\mathbf{S} (\mathbf{S}^{-1} \mathbf{v}) = \mathbf{v}
</math>

which shows that

:<math>
\mathbf{v} = \sum_{k} \langle \mathbf{v} \mid \tilde{\mathbf{e}}_{k} \rangle \mathbf{e}_{k}
</math>

This derivation of the 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 dual frame.

== See also ==
* [[Frame (linear algebra)]]
* [[k-frame|''k''-frame]]
* [[Restricted isometry property]]

== References ==

* {{cite book
| author=Ole Christensen
| title=An Introduction to Frames and Riesz Bases
| year=2003
| publisher=Birkhäuser
}}

* {{cite journal
| author=R. J. Duffin and A. C. Schaeffer
| title=A class of nonharmonic Fourier series
| year=1952
| journal=Trans. Amer. Math. Soc.
| volume= 72
| pages=341–366
| doi=10.2307/1990760
| jstor=1990760
| issue=2
| publisher=Transactions of the American Mathematical Society, Vol. 72, No. 2
}}

* {{cite journal
| author=Jelena Kovacevic, Pier Luigi Dragotti, and Vivek Goyal
| title=Filter Bank Frame Expansions with Erasures
|date=June 2002
| journal=IEEE Trans. Information Theory
| volume=48
| issue=6
| pages=1439–1450
| url=http://citeseer.ist.psu.edu/cache/papers/cs/28168/http:zSzzSzlcavwww.epfl.chzSz~dragottizSzpublicationszSzIT_june02.pdf/kovacevic02filter.pdf
| doi=10.1109/TIT.2002.1003832
}}

{{DEFAULTSORT:Frame Of A Vector Space}}
[[Category:Linear algebra]]
[[Category:Differential geometry]]

Minkowski plane - Revision history

en>Ag2gaeh: /* Miquelian Minkowski planes */ hint on the non existence of "ovoidal Minkowski planes" added