2.1 Bases and frames

A set $\Psi ={\left\{{\psi }_i\right\}}_{i\in \mathcal{I}}$ is called a basis for a finite-dimensional vector space $\mathcal{V}$ if the vectors in the set span $\mathcal{V}$ and are linearly independent. This implies that each vector in the space can be represented as a linear combination of this (smaller, except in the trivial case) set of basis vectors in a unique fashion. Furthermore, the coefficients of this linear combination can be found by the inner product of the signal and a dual set of vectors. In discrete settings, we will only consider real finite-dimensional Hilbert spaces where $\mathcal{V}={\mathbb{R}}^N$ and $\mathcal{I}=\{1,...,N\}$ .

Mathematically, any signal $x\in {\mathbb{R}}^N$ may be expressed as,

where our coefficients are computed as $a_i=⟨x,{\psi }_i⟩$ and ${\left\{\widetilde{{\psi }_i}\right\}}_{i\in I}$ are the vectors that constitute our dual basis. Another way to denote our basis and its dual is by how they operate on $x$ . Here, we call our dual basis $\tilde{\Psi }$ our synthesis basis (used to reconstruct our signal by [link] ) and $\Psi$ is our analysis basis .

An orthonormal basis (ONB) is defined as a set of vectors $\Psi ={\left\{{\psi }_i\right\}}_{i\in \mathcal{I}}$ that form a basis and whose elements are orthogonal and unit norm. In other words, $⟨{\psi }_i,{\psi }_j⟩=0$ if $i\ne j$ and one otherwise. In the case of an ONB, the synthesis basis is simply the Hermitian adjoint of analysis basis ( $\tilde{\Psi }={\Psi }^T$ ).

It is often useful to generalize the concept of a basis to allow for sets of possibly linearly dependent vectors, resulting in what is known as a frame . More formally, a frame is a set of vectors ${\left\{{\Psi }_i\right\}}_{i=1}^n$ in ${\mathbb{R}}^d$ , $d<n$ corresponding to a matrix $\Psi \in {\mathbb{R}}^{d\times n}$ , such that for all vectors $x\in {\mathbb{R}}^d$ ,

with $0<A\le B<\infty$ . Note that the condition $A>0$ implies that the rows of $\Psi$ must be linearly independent. When $A$ is chosen as the largest possible value and $B$ as the smallest for these inequalities to hold, then we call them the (optimal) frame bounds . If $A$ and $B$ can be chosen as $A=B$ , then the frame is called $A$ -tight , and if $A=B=1$ , then $\Psi$ is a Parseval frame . A frame is called equal-norm , if there exists some $\lambda >0$ such that ${∥{\Psi }_i∥}_2=\lambda$ for all $i=1,...,N$ , and it is unit-norm if $\lambda =1$ . Note also that while the concept of a frame is very general and can be defined in infinite-dimensional spaces, in the case where $\Psi$ is a $d\times N$ matrix $A$ and $B$ simply correspond to the smallest and largest eigenvalues of $\Psi {\Psi }^T$ , respectively.

Frames can provide richer representations of data due to their redundancy: for a given signal $x$ , there exist infinitely many coefficient vectors $\alpha$ such that $x=\Psi \alpha$ . In particular, each choice of a dual frame $\tilde{\Psi }$ provides a different choice of a coefficient vector $\alpha$ . More formally, any frame satisfying

is called an (alternate) dual frame. The particular choice $\tilde{\Psi }={\left(\Psi {\Psi }^T\right)}^{-1}\Psi$ is referred to as the canonical dual frame . It is also known as the Moore-Penrose pseudoinverse. Note that since $A>0$ requires $\Psi$ to have linearly independent rows, we ensure that $\Psi {\Psi }^T$ is invertible, so that $\tilde{\Psi }$ is well-defined. Thus, one way to obtain a set of feasible coefficients is via

One can show that this sequence is the smallest coefficient sequence in ${\ell }_2$ norm, i.e., ${∥{\alpha }_d∥}_2\le {∥\alpha ∥}_2$ for all $\alpha$ such that $x=\Psi \alpha$ .

Finally, note that in the sparse approximation literature, it is also common for a basis or frame to be referred to as a dictionary or overcomplete dictionary respectively, with the dictionary elements being called atoms .