

International conference on Function Spaces and Approximation Theory dedicated to the 110th anniversary of S. M. Nikol'skii
May 27, 2015 10:00–10:40, Пленарные доклады, Moscow, Steklov Mathematical Institute of RAS






Sparse approximation with respect to the trigonometric system
V. N. Temlyakov^{ab} ^{a} Steklov Mathematical Institute of Russian Academy of Sciences
^{b} University of South Carolina, USA

Number of views: 
This page:  248  Video files:  123  Materials:  91 
Photo Gallery

Abstract:
Sparse approximation with respect to dictionaries is a very important topic in the highdimensional 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 HahnBanach 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,…,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)} \fs\_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_{m1}}(\varphi_m) \ge t\sup_{g\in {\mathcal D}} F_{f_{m1}}(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 := fG_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, …$ 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 Lebesguetype 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 Lebesguetype inequality guarantees that the WCGA works very well for each individual function $f$.
Materials:
abstract.pdf (105.2 Kb)
Language: English

