2.2 Sparse approximation and ℓp spaces

We now look at how well $f\in \mathbf{X}$ can be approximated by $n$ functions in the dictionary $\mathcal{D}$ .

We define the error of $n$ -term approximation of $f$ by the elements of the dictionary $\mathcal{D}$ as $$\begin{array}{cc}\text{(1)}& \sigma {}_n\left(f\right){}_{\mathbf{X}}:=\sigma {}_n(f,\mathcal{D}){}_X:=\text{inf}{}_{s\in {\mathrm{\Sigma }}_n}\parallel f-s\parallel {}_{\mathbf{X}}.\end{array}$$

We also define the class of $r$ -smooth signals in $\mathcal{D}$ as $$\begin{array}{cc}\text{(2)}& \mathcal{A}{}^r:=\mathcal{A}{}^r\left(\mathcal{D}\right):=\mathit{\{}f\in X,\sigma {}_n(f)\le Mn{}^{-r}\text{ for some }M\mathit{\}}\end{array}$$ ,

with the corresponding norm ${\parallel f\parallel }_{{\mathcal{A}}^r}={sup}_{n=1,2,\mathrm{\dots }}{\mathcal{n}}^r{\sigma }_n{\left(f\right)}_{\mathbf{X}}$ .

In general, the larger $r$ is, the 'smoother' the function $s\in {\mathcal{A}}^r{\left(\mathcal{D}\right)}_{\mathbf{X}}$ . Note also that ${\mathcal{A}}^r\subseteq {\mathcal{A}}^{r^{\prime }}$ if $r>r^{\prime }$ . Given $f$ , let $r\left(f\right)=\text{sup}\left\{r:f\in {\mathcal{A}}^r\right\}$ be a measure of the "smoothness" of $f$ , i.e. a quantification of compressibility.

Let $\mathbf{X}=H$ , a Hilbert space

Recall the definition of ${\mathrm{\ell }}_p$ spaces: let $\left(a_j\right)\in \mathbb{R}$ ; then $\left(a_j\right)\in {\mathrm{\ell }}_p$ if ${\parallel \left(a_j\right)\parallel }_{{\mathrm{\ell }}_p}<\infty$ with ${\parallel \left(a_j\right)\parallel }_{{\mathrm{\ell }}_p}={\left({\sum }_j{\left|a_j\right|}^p\right)}^{1/p}$ for $p<\mathrm{\infty }$ and ${\parallel \left(a_j\right)\parallel }_{{\mathrm{\ell }}_p}={sup}_j\left|a_j\right|$ for $p=\mathrm{\infty }$ . We also recall that for $L_p$ spaces on compact sets, $L_p\subset L_{p^{\prime }}$ if $p>p^{\prime }$ . The opposite is true for ${\mathrm{\ell }}_p$ spaces: ${\mathrm{\ell }}_p\subset {\mathrm{\ell }}_{p^{\prime }}$ if $p<p^{\prime }$ . Hence, the smaller the value of $p$ is, the “smaller” ${\mathrm{\ell }}_p$ is.

A sequence $\left(a_n\right)$ is in ${\mathrm{\ell }}_p$ if the sorted magnitudes of the $a_n$ decay faster than $n^{\mathrm{-}\frac{1}{p}}$ .

Define $a_n^{*}$ as the element of the sequence $\left(a_n\right)$ with the $n^{\text{th}}$ largest magnitude, and denote $\left(a_n^{*}\right)$ as the decreasing rearrangement of $\left(a_n\right)$ . It is easy to show that $k{\left(a_k^{*}\right)}^p\le {\sum }_n{\left(a_n\right)}^p$ for all $k$ ; also, if $\left(a_n\right)\in {\mathrm{\ell }}_p$ , then $a_k^{*}\le {\parallel \left(a_n\right)\parallel }_{{\mathrm{\ell }}_p}{k}^{-\frac{1}{p}}$ .

A sequence $\left(a_n\right)$ is in weak ${\mathrm{\ell }}_p$ , denoted $\left(a_n\right)\in w{\mathrm{\ell }}_p$ , if $a_k^{*}\le M{k}^{-\frac{1}{p}}$ . We also define the quasinorm

For $p$ , $p^{\mathrm{\prime }}$ such that $p^{\mathrm{\prime }}\mathrm{>}p$ , we have ${\mathrm{\ell }}_p\mathrm{\subset }w{\mathrm{\ell }}_p\mathrm{\subset }{\mathrm{\ell }}_{p^{\mathrm{\prime }}}$ .

Let $\mathcal{D}\mathrm{=}B$ be an orthonormal basis for the Hilbert space $\mathbf{X}\mathrm{=}H$ . For $f\mathrm{\in }\mathbf{X}$ with representation in $B\mathrm{=}\left[{\varphi }_1,{\varphi }_2,\mathrm{\dots }\right]$ as $f\mathrm{=}{\mathrm{\sum }}_n{c}_n\left(f\right){\varphi }_n$ , we have $f\mathrm{\in }{\mathrm{A}}^r{\left(B\right)}_{\mathbf{X}}$ if and only if the sequence $\left(c_n\left(f\right)\right)\mathrm{\in }w{\mathrm{\ell }}_{\tau }$ , with $\frac{1}{\tau }\mathrm{=}r\mathrm{+}\frac{1}{2}$ . Moreover, there exist $C_0,C_0^{\mathrm{\prime }}\mathrm{\in }\mathbb{R}$ such that $C_0^{\mathrm{\prime }}{\parallel \left(c_n\left(f\right)\right)\parallel }_{w{\mathrm{\ell }}_{\tau }}\mathrm{\le }{\parallel f\parallel }_{{\mathrm{A}}^r}\mathrm{\le }{C}_0{\parallel \left(c_n\left(f\right)\right)\parallel }_{w{\mathrm{\ell }}_{\tau }}$ .

We prove the converse statement; the forward statement proof is left to the reader. We would like to show thatif $\left(c_n\left(f\right)\right)\in w{\mathrm{\ell }}_{\tau }$ , then $f\in {\mathcal{A}}^r$ , with $r=\frac{1}{\tau }-\frac{1}{2}$ . The best $n$ -term approximation of $f$ in $B$ is of the form $s={\sum }_{k\in \mathrm{\Lambda }}{a}_k{\varphi }_k,\mathrm{♯}\mathrm{\Lambda }\le n$ . Therefore, we have: $$\begin{array}{cc}\text{(3)}& \begin{array}{ccc}\hfill {\sigma }_n{\left(f\right)}_{\mathbf{X}}& \hfill =\hfill & \underset{s\in {\mathrm{\Sigma }}_n}{\text{inf}}{\parallel f-s\parallel }_{\mathbf{X}}=\underset{s\in {\mathrm{\Sigma }}_n}{\text{inf}}{\parallel \sum _{k\in \mathrm{\Lambda }}\left(c_k\left(f\right)-a_k\right){\varphi }_k+\sum _{k\notin \mathrm{\Lambda }}{c}_k\left(f\right){\varphi }_k{}_{}\parallel }_X\hfill \\ & \hfill =\hfill & \underset{s\in \mathrm{\Lambda }}{\text{inf}}\sum _{k\in \mathrm{\Lambda }}{\left(c_k\left(f\right)-a_k\right)}^2+\sum _{k\notin \mathrm{\Lambda }}{\left(c_k\left(f\right)\right)}^2=\sum _{k=n+1}^{\mathrm{\infty }}{\left|c_k^{*}\left(f\right)\right|}^2\hfill \\ & \hfill \le \hfill & M^2\sum _{k=n+1}^{\mathrm{\infty }}{k}^{-\frac{2}{\tau }}\le M^2\sum _{k=n+1}^{\mathrm{\infty }}{k}^{-2r-1}\text{ (since }\left(c_n\left(f\right)\right)\in w{\mathrm{\ell }}_p\text{)},\hfill \end{array}\end{array}$$

where $M:=\parallel \left(c{}_n\right(f)\parallel {}_{w{\mathrm{\ell }}_p}$ .

We prove the converse statement; the forward statement proof is left to the reader. We would like to show thatif $\left(c_n\left(f\right)\right)\in w{\mathrm{\ell }}_{\tau }$ , then $f\in {\mathcal{A}}^r$ , with $r=\frac{1}{\tau }-\frac{1}{2}$ . The best $n$ -term approximation of $f$ in $B$ is of the form $s={\sum }_{k\in \mathrm{\Lambda }}{a}_k{\varphi }_k,\mathrm{♯}\mathrm{\Lambda }\le n$ . Therefore, we have: $$\begin{array}{cc}\text{(3)}& \begin{array}{ccc}\hfill {\sigma }_n{\left(f\right)}_{\mathbf{X}}& \hfill =\hfill & \underset{s\in {\mathrm{\Sigma }}_n}{\text{inf}}{\parallel f-s\parallel }_{\mathbf{X}}=\underset{s\in {\mathrm{\Sigma }}_n}{\text{inf}}{\parallel \sum _{k\in \mathrm{\Lambda }}\left(c_k\left(f\right)-a_k\right){\varphi }_k+\sum _{k\notin \mathrm{\Lambda }}{c}_k\left(f\right){\varphi }_k{}_{}\parallel }_X\hfill \\ & \hfill =\hfill & \underset{s\in \mathrm{\Lambda }}{\text{inf}}\sum _{k\in \mathrm{\Lambda }}{\left(c_k\left(f\right)-a_k\right)}^2+\sum _{k\notin \mathrm{\Lambda }}{\left(c_k\left(f\right)\right)}^2=\sum _{k=n+1}^{\mathrm{\infty }}{\left|c_k^{*}\left(f\right)\right|}^2\hfill \\ & \hfill \le \hfill & M^2\sum _{k=n+1}^{\mathrm{\infty }}{k}^{-\frac{2}{\tau }}\le M^2\sum _{k=n+1}^{\mathrm{\infty }}{k}^{-2r-1}\text{ (since }\left(c_n\left(f\right)\right)\in w{\mathrm{\ell }}_p\text{)},\hfill \end{array}\end{array}$$

where we define $C=\frac{{\lambda }_0}{r}$ . Using this result in the earlier statement, we get $$\begin{array}{cc}\text{(5)}& \begin{array}{ccc}\hfill \sum _{k=n+1}^{\mathrm{\infty }}{\left|c_k^{*}\left(f\right)\right|}^2& \hfill \le \hfill & C{M}^2{n}^{-2r}\le M^{2}z{n}^{-r};\hfill \end{array}\end{array}$$

this implies by definition that $\left(c_k\left(f\right)\right)\in {\mathcal{A}}^r$ .