Highly Nonlinear Approximations for Sparse Signal Representation


Frames and bases for finite a dimension vector space

If $ v_1,\ldots,v_n$ are some elements of a vector space $ {\cal{V}}$, by a linear combination of $ v_1,\ldots,v_n$ we mean an element in $ {\cal{V}}$ of the form $ a_1 v_1 + \cdots +a_n v_n$, with $ a_i \in \mathbb{F}, i=1,\ldots,n$.

Let $ S$ be a subset of element of $ {\cal{V}}$. The set of all linear combinations of elements of $ S$ is called the span of $ S$ and is denoted by $ {\mbox{\rm {span}}}  S$.

A subset $ S=\{v_i\}_{i=1}^n$ of $ {\cal{V}}$ is said to be linearly independent if and only if

$\displaystyle a_1 v_1 + \cdots +a_n v_n= 0,\quad \implies \quad a_i=0, i=1,\ldots,n.$

A subset is said to be linearly dependent if it is not linearly independent.

$ {\cal{S}}$ is said to be a basis of $ {\cal{V}}$ if it is linearly independent and $ {\mbox{\rm {span}}}  S={\cal{V}}$. The dimension of a finite dimensional vector space $ {\cal{V}}$ is the number of elements in a basis for $ {\cal{V}}$. The number of elements in a set is termed the cardinality of the set.

If the number of elements spanning a finite dimensional vector space $ {\cal{V}}$ is larger than the number of elements of a basis for the same space, the set is called a redundant frame. In other words a redundant frame (henceforth called simply a frame) for a finite dimensional vector space $ {\cal{V}}$ is a linearly dependent set of vectors spanning $ {\cal{V}}$.

Let $ \{v_i\}_{i=1}^n$ be a spanning set for $ {\cal{V}}$. Then every $ v \in {\cal{V}}$ can be expressed as

$\displaystyle v= a_1 v_1 + \cdots, a_n v_n,$   with$\displaystyle ,\quad a_i \in \mathbb{F}, i=1,\ldots,n.$

If the spanning set $ \{v_i\}_{i=1}^n$ is a basis for $ {\cal{V}}$ the numbers $ a_i \in \mathbb{F}, i=1,\ldots,n$ in the above decomposition are unique. In the case of a redundant frame, however, these numbers are not longer unique. For further discussion about redundant frames in finite dimension see [1].