Sparse approximation with respect to the trigonometric system

Sparse approximation with respect to dictionaries is a very important topic in the high-dimensional approximation. The main motivation for the study of sparse approximation is that many real world signals can be well approximated by sparse ones. Sparse approximation automatically implies a need for nonlinear approximation, in particular, for greedy approximation. We give a brief description of a sparse approximation problem and present a discussion of the obtained results and their relation to previous work. In a general setting we are working in a Banach space $X$ with a redundant system of elements $\mathcal D$ (dictionary $\mathcal D$). There is a solid justification of importance of a Banach space setting in numerical analysis in general and in sparse approximation in particular. Let $X$ be a real Banach space with norm $\|\cdot\|:=\|\cdot\|_X$. We say that a set of elements (functions) $\mathcal D$ from $X$ is a dictionary if each $g\in \mathcal D$ has norm one ($\|g\|=1$), and the closure of span $\mathcal D$ is $X$. A symmetrized dictionary is $\mathcal D^\pm:=\{\pm g:g\in \mathcal D\}$. For a nonzero element $g\in X$ we let $F_g$ denote a norming (peak) functional for $g$:
$$ \|F_g\|_{X^*} =1,\qquad F_g(g) =\|g\|_X. $$
The existence of such a functional is guaranteed by the Hahn-Banach theorem.
An element (function, signal) $s\in X$ is said to be $m$-sparse with respect to $\mathcal D$ if it has a representation $s=\sum_{i=1}^mc_ig_i$, $g_i\in \mathcal D$, $i=1,\dots,m$. The set of all $m$-sparse elements is denoted by $\Sigma_m(\mathcal D)$. For a given element $f$ we introduce the error of best $m$-term approximation
$$ \sigma_m(f,\mathcal D)_X := \inf_{s\in\Sigma_m(\mathcal D)} \|f-s\|_X. $$

Let $t\in (0,1]$ be a given nonnegative number. We define the Weak Chebyshev Greedy Algorithm (WCGA) that is a generalization for Banach spaces of Weak Orthogonal Greedy Algorithm .
Weak Chebyshev Greedy Algorithm (WCGA).
We define $f_0 := f$. Then for each $m\ge 1$ we inductively define

• 1) $\varphi_m \in {\mathcal D}$ is any element satisfying
  $$ |F_{f_{m-1}}(\varphi_m)| \ge t\sup_{g\in {\mathcal D}} |F_{f_{m-1}}(g)|; $$
  
  
• 2) define
  $$ \Phi_m := \operatorname{span} \{\varphi_j\}_{j=1}^m, $$
  and define $G_m $ to be the best approximant to $f$ from $\Phi_m$;
  
• 3) denote
  $$ f_m := f-G_m. $$
  

We demonstrated that the Weak Chebyshev Greedy Algorithm (WCGA) is very good for $m$-term approximation with respect to a special class of dictionaries, in particular, for the trigonometric system. The trigonometric system is a classical system that is known to be difficult to study. We studied among other problems the problem of nonlinear sparse approximation with respect to it. Let ${\mathcal R}{\mathcal T}$ denote the real trigonometric system $1,\sin 2\pi x,\cos 2\pi x, \dots$ on $[0,1]$ and let ${\mathcal R}{\mathcal T}_p$ to be its version normalized in $L_p([0,1])$. Denote ${\mathcal R}{\mathcal T}_p^d := {\mathcal R}{\mathcal T}_p\times\cdots\times {\mathcal R}{\mathcal T}_p$ the $d$-variate trigonometric system. We need to consider the real trigonometric system because the algorithm WCGA is well studied for the real Banach space. We proved the following Lebesgue-type inequality for the WCGA.
Theorem. Let $\mathcal D$ be the normalized in $L_p$, $2\le p<\infty$, real $d$-variate trigonometric system. Then for any $f\in L_p$ the WCGA with weakness parameter $t$ gives
$$ \|f_{C(t,p,d)m\ln (m+1)}\|_p \le C\sigma_m(f,\mathcal D)_p . $$

The above Lebesgue-type inequality guarantees that the WCGA works very well for each individual function $f$.