2.3 Thresholding and greedy bases

We shall next discuss some notions related to best $n$ -term approximation.

Thresholding

• Let $\mathbb{X}$ be a Hilbert space. Given $f$ , let ${\Lambda }_{ϵ}\left(f\right)=\{j:|c_j\left(f\right)|>ϵ\}$ . The thresholding operator $T_{ϵ}$ is defined by
  $$T_{ϵ}f=\sum _{j\in {\Lambda }_{ϵ}\left(f\right)}{C}_j\left(f\right){\phi }_j.$$
  It is easy to see that for each $ϵ$ , $T_{ϵ}f$ is the best approximation to $f$ using $N$ terms where $N$ is the cardinality of ${\Lambda }_{ϵ}$ :
  $$\parallel f-T_{ϵ}{\parallel }_{\mathbb{X}}={\sigma }_N(f{)}_{\mathbb{X}}.$$
  Thresholding is easily implemented on a computer.
• The thresholding scheme above can be generalized if $\mathbb{X}$ is not a Hilbert space provided the dictionary has some specific structure. For example, when
  • The dictionary is the wavelet basis and $\mathbb{X}=L_p$ , $1<p<\infty$ .
  • $\mathbb{X}=l_p$ and the dictionary is the canonical basis ${\delta }_j={\phi }_j$ . ex: $(0,0,...,1,0)$
  • For a general Banach space $\mathbb{X}$ and the dictionary $\left({\phi }_j\right)$ is a greedy basis.

Greedy bases

We briefly describe the notion of greedy basis.

Given $\mathbb{X}$ , we say $\left({\phi }_j\right)$ is a greedy basis for $\mathbb{X}$ if for each $ϵ>0$ ,

where $N$ is the cardinality of ${\Lambda }_{ϵ}$ .

A basis ${\phi }_j$ is said to be unconditional if

or equivalently

This is an older concept from functional analysis. In words, this definition says that if the terms $c_j$ are rearranged, the series $\sum c_j{\phi }_j$ will still converge. This is not generally true for all bases.

A basis ${\phi }_j$ is said to be democratic if

where the cardinality of ${\Lambda }^{\text{'}}$ equals the cardinality of $\Lambda$ .

$\left({\phi }_j\right)$ greedy $\leftrightarrow$ $\left({\phi }_j\right)$ is both unconditional and democratic.

Some examples involving the last two definitions:

• The fourier basis in $L_p$ is not democratic, but is unconditional for $l<p<\infty$ .
• The wavelet basis contains both of these properties, and is therefore greedy.

If $\mathbb{X}=L_p$ has $\left({\phi }_j\right)$ greedy, $B=\left\{{\phi }_j\right\}$ , $f={\sum }_{j=1}^{\infty }{c}_j\left(f\right){\phi }_j$ , $c_j\left(f\right)=〈f,,,{\psi }_j〉$ where ${\psi }_j$ is a dual basis,

and

Let us now consider a specific setting that we shall be concerned with a lot in this course. We shall examine some of the conceptswe have introduced in the finite dimensional space of of all sequence (points) in ${\mathbb{R}}^N$ . Recall that we can put many different norms on this space including the ${\ell }_p$ norms and the weak ${\ell }_p$ norms.

Given a vector $=(x_1,x_2,...,x_N)\in {\mathbb{R}}^N$ . The best approximation to $x$ from ${\Sigma }_n$ in the ${\ell }_p$ norm is to take the vector in ${\Sigma }_n$ which shares the $n$ largest values of $x$ . Its error of approximation satisfies

$\parallel x{\parallel }_{w_{l_{\tau }}}\le \parallel x{\parallel }_{l_{\tau }},\frac{1}{\tau }=r+\frac{1}{p}$ .

For $p=1$ and $r=3$ , ${\sigma }_n(x{)}_{{\ell }_1}\le C{n}^{-3}\parallel x{\parallel }_{w_{l_{\tau }}}$ and $\frac{1}{\tau }=4$ . In words, this equation shows what kind of $\tau$ is needed for a given decay rate (or given some $\tau$ , what kind of decay rate will be achieved) to approximate with certain ability.

Show ${\sigma }_n(x{)}_{l_p}\le C{n}^{-r}\parallel x{\parallel }_{l_{\tau }}$ holds with $C=1$ .

Proof: Let ${\Lambda }_n:=\{i:|x_i\left|\mathrm{largest}\right\}$ ,

and so

${\sigma }_n(x{)}_{l_p}\le n^{-r}\parallel x{\parallel }_{l_{\tau }}$

For $\mathbb{X}=L_p$ , $\left\{{\phi }_j\right\}$ a wavelet basis, we can say wavelet coefficients of $f$ are in $l_p$ is equivalent to $f$ is in a certain Besov class (roughly speaking $f$ has $r$ derivatives and $f^{\left(r\right)}\in L_{\tau }$ ). We refer the reader to for precise formulations of results of this type.