Preliminaries

We previously described Shannon's Theorem plus encoding: the Nyquist sampling rate is the minimal required sampling rate torecover the entire class of bandlimited signals. We have seen that this sampling rate may be prohibitively large forbroadband signals. We see a way to improve upon this situation: we will pose a different model for the signals which is morerestrictive than the assumption that the signals are bandlimited. Fortunately, there are several real world scenarios in which oneknows much more information about the signals of interest. For example, they may be written in terms of very few fundamentalbuilding blocks (such as sine waves or chirps). This leads us to define new signal classes based on notions of sparsity and seek to determine if we can improve on sampling and encoding in this new setting.

Let us define the general setting for this section. Let $\mathbf{X}$ be a Banach space of functions. The typical examples are $\mathbf{X}=L_p\left(\mathbb{R}\right),L_p\left({\mathbb{R}}^d\right),L_p\left(-T,T\right)$ , $1\le p\le \mathrm{\infty }$ . We denote the norm on $X$ by $\parallel \cdot \parallel {}_{\mathbf{X}}$ . We define a dictionary $\mathcal{D}$ as any collection of functions $\mathcal{D}\subseteq \mathbf{X}$ such that ${\parallel g\parallel }_{\mathbf{X}}=1$ for all $g\in \mathcal{D}$ , i.e. all the elements of the dictionary are normalized. While thedefinition is very broad, in practice dictionaries usually have more structure. Some examples include $\mathcal{D}=B$ , a basis for $\mathbf{X}$ , such as (i) the Fourier basis on $\left[-\pi ,\pi \right]$ , (ii) a wavelet basis,

We define the class of $n$ -sparse signals as $\mathrm{\Sigma }{}_n:=\mathrm{\Sigma }{}_n\left(\mathcal{D}\right)=\mathit{\{}s=\sum {}_{g\in \mathrm{\Lambda }}c{}_{g}g,\mathrm{\Lambda }\subseteq \mathcal{D},\mathrm{♯}\mathrm{\Lambda }\le n\mathit{\}}$ . We also say that $s$ has sparsity $n$ in $\mathcal{D}$ if $s\in {\mathrm{\Sigma }}_n\left(\mathcal{D}\right)$ , i.e. if it can be written as the linear combination of $n$ functions from $\mathcal{D}$ . We note that ${\mathrm{\Sigma }}_n$ is not a linear space; we instead have ${\mathrm{\Sigma }}_n+{\mathrm{\Sigma }}_n\subseteq {\mathrm{\Sigma }}_{2n}$ .